\chapter{算法}
\section{递归}
\subsection{数的次方}
\begin{example}[变量a的n次方]
    \begin{equation}
        a^n =
        \begin{cases}
             & a^{\frac{n}{2}}\cdot a^{\frac{n}{2}}       \\
             & a^{\frac{n-1}{2}}\cdot a^{\frac{n-1}{2}}*a
        \end{cases}
    \end{equation}
\end{example}
\cppfile[firstline=1,lastline=19]{code/offer/ex20/main.cpp}
\subsection{8皇后问题}
\cppfile[firstline=1,lastline=83]{code/arith/main.cpp}
\subsection{通过递归实现字符的反向输出}
函数调用的时候进栈，如果函数接受的输入不是回车函数将递归调用自身，再次进栈，知道输入回车，最后一次调用的函数线运行，输出当前栈中的元素，然后出栈，然后依次出栈实现字符的反向输出。
\cppfile[firstline=1,lastline=13]{code/arith/recursive/ex1/ex1.cc}
\subsection{迷宫}
初始位置在m，m的位置(3,3)进栈，上下左右查找能走的方向，发现(2 3),(3 2)能走，于是将其压栈(b)。当前位置设置为栈顶元素(3 2)同时查找能走的方向，找到(2 2)和(3 1)压栈，依次知道找到目标e（h）,找到目标退出。
\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{maze}
\end{figure}
\subsection{辗转相除法求最大公约数}
\begin{algorithm}
    \caption{辗转相除法求最大公约数}
    \label{al:al1}
    \begin{algorithmic}
        \REQUIRE $a>b$
        \WHILE{$b\neq0 $}
        \STATE $a = b,b\qquad mod\qquad r$
        \ENDWHILE
    \end{algorithmic}
\end{algorithm}
\cppfile[firstline=1,lastline=28]{code/DS/ex11/test1.cc}
% 这时候第一个不匹配的字符串的左边的字符串为a，长度为1.不存在其左右字符相等，这时候next[1] = 0;
% \begin{figure}[!htbp]
% \centering
% \includegraphics[width=0.5\textwidth]{kmp5.pdf}
% \caption{P[k] = P[j]}
%     \label{fig:kmp_7}
% \end{figure}
% 
% 当$P[k]=P[j]$时，有$next[j+1] = next[j]+1$,这是因为在$P[j]$之前已经有$P[0:k-1] = p[j-k:j-1],AB=AB$,这时候$P[k] = P[j],C=C$，我们是不是可以得到$P[0:k-1]+P[k]=p[j-k:j-1]+P[j],ABC=ABC$。即$P[0:K] = P[j-k:j]$即$next[j+1]=k+1=next[j]+1$。
% 如果$P[k]\neq P[j]$则$k = next[k]$。
% 
% 看上面的例子，我们已经不可能找到ABAB这个最长的串了，但是我们还是可能找到[A,B],[B]这样的串。所以这个过程不像再定位[A,B,A,C]这个串，当C和主串不一样了（也就是k位置不一样了），那当然是把指针移动到next[k]。
% \begin{figure}[!htbp]
% \centering
%     \subfigure[字符串]{\includegraphics[width=0.4\textwidth,height=1.5cm]{kmp1.png}}
%     \subfigure[匹配]{\includegraphics[width=0.4\textwidth,height=1.5cm]{kmp2.png}}
%     \label{fig:kmp_7}
% \end{figure}
% 从匹配的结果看：
% \[t_{i-j}\quad t_{i-j+1} \quad t_{i-j+2}\quad t_{i-1} = p_0\quad p_1\quad p_2\cdots p_{j-1}\]
% 朴素匹配的下一趟
% \[p_0\qquad p_1 \cdots p_{j-2}\neq p_1\qquad p_2\qquad\cdots p_{j-1}\]
% 字符串的特征向量构造方法:
% \begin{equation*}
%     next[j]=\begin{cases}
%         -1\quad j=0\\
%         max\left\{k:0<k<j\&p[0\cdots k-1]=p[j-k\cdots j-1] \right\}\\
%         0\quad 其它
%     \end{cases}
% \end{equation*}
% 计算字符串的模式匹配字符串P = a a a a b a a a a c,计算j对应位置的前一位j-1子序列的真子序列相等的最大长度。
% \begin{itemize}
% \item j=0,next[0] = -1
% \item j=1,0<k<j,k没有值，next[1] = 0
% \item j=2,k=1,next[2] = 1
% \item j=3,k=1,2,next[3] = 2
% \item j=4,k=1,2,3,next[4] = 3
% \item j=5,k=1,2,3,4,next[5] = 0
% \item j=6,k=1,2,3,4,5,next[6] = 1
% \item j=7,k=1,2,3,4,5,6,next[7] = 2
% \item j=8,k=1,2,3,4,5,6,7,next[8] = 3
% \item j=[9],k=1,2,3,4,5,6,7,next[9] = 4
% \end{itemize}
% \begin{figure}[!htbp]
% \centering
% \includegraphics[width=\textwidth]{kmp3.png}
%     \label{fig:kmp_8}
% \caption{kmp匹配示意图}
% \end{figure}
% \begin{figure}[!htbp]
% \centering
% \includegraphics[width=\textwidth]{kmp3.png}
% \caption{kmp匹配示意图
% \end{figure}
\textbf{求解特征向量的算法框架}\\
特征数$n_j(j>0,0\leq n_{j+1} \leq j)$是递归定义的：
\begin{enumerate}
    \item $n_0=-1$,对于j>0的$n_{j+1}$,假定已知前一位的特征数$n_j$，令$k=n_j$
    \item 当$k\geq 0$且$p_j\neq p_k$时，则令$k = n_k$;让步骤2循环到条件不满足
    \item $n_{j+1}$ 此时k == -1或者 $p_j == p_k$
\end{enumerate}
kmp算法框架：
\begin{enumerate}
    \item 分别从target和parttern第一位开始向后依次匹配。找到第一位失配的位置。将parttern第next[i]位移动到失配位置。
    \item 如果失配出现在parttern第一位则将next[0]移动到失配位置。因为next[0]为-1。将-1移动到失配位置，这时候相当于字符串整体右移一格。
    \item 如果匹配到整个parttern末尾，说明匹配，返回位置为target指向的位置和parttern指向位置的差。
\end{enumerate}
\cppfile[firstline=1,lastline=66]{code/string/ex4/main.cpp}
\section{排序算法}
\begin{definition}[稳定性]
    如果a原本在b的前面且a=b排序后a仍然在b的前面，则成为稳定排序,否则称为不稳定排序。
\end{definition}
\begin{table}[!htbp]
    \begin{tabular}{lllllll}
        \toprule
        排序算法  & 时间复杂度     & 最好情况       & 最坏情况       & 空间复杂度 & 排序方式 & 是否为稳定排序 \\
        \midrule
        冒泡排序  & $O(n^2)$       & $O(n)$         & $O(n^2)$       & $O(1)$     & 原地     & 是             \\
        选择排序  & $O(n^2)$       & $O(n^2)$       & $O(n^2)$       & $O(1)$     & 原地     & 否             \\
        插入排序  & $O(n^2)$       & $O(n)$         & $O(n^2)$       & $O(1)$     & 原地     & 是             \\
        shell排序 & $O(nlogn)$     & $O(nlogn)$     & $O(nlong)$     & $O(1)$     & 原地     & 否             \\
        归并排序  & $O(nlogn)$     & $O(nlogn)$     & $O(nlogn)$     & $O(n)$     & 非原地   & 是             \\
        快速排序  & $O(nlogn)$     & $O(nlogn)$     & $O(n^2)$       & $O(logn)$  & 原地     & 否             \\
        堆排序    & $O(nlogn)$     & $O(nlogn)$     & $O(nlogn)$     & $O(1)$     & 原地     & 否             \\
        计数排序  & $O(n+k)$       & $O(n+k)$       & $O(n+k)$       & $O(k)$     & 非原地   & 是             \\
        桶排序    & $O(n+k)$       & $O(n+k)$       & $O(n^2)$       & $O(n+k)$   & 非原地   & 是             \\
        基数排序  & $O(n\times k)$ & $O(n\times k)$ & $O(n\times k)$ & $O(n+k)$   & 非原地   & 是             \\
        \bottomrule
    \end{tabular}
    \caption{排序算法性能}
\end{table}
\subsection{选择排序}
将待排序的数组中最小元素和数组中第一个元素交换（如果最小的元素就是第一个元素就自己和自己交换），然后依次在剩余的数组中找到最小的元素将其和待排序的数组中第二个元素交换，一直到结束。
\begin{itemize}
    \item 时间复杂度：$O(n^2)$
    \item 空间复杂度：$O(1)$
    \item 非稳定排序
    \item 原地排序
\end{itemize}
\cppfile{code/arith/ex96/include/choose_sort.cpp}
\subsection{快速排序}
\begin{algorithm}[!htbp]
    \caption{快速排序}
    \label{al:al2}
    \begin{algorithmic}
        \STATE 数组长度为n，索引下标为1
        \WHILE{数组不是全局有序}
        \STATE 选择轴值，将序列划分乘两个子序列L和R，使得L中所有记录小于或者等于轴值，R中记录都大于轴值。
        \IF{如果数组全局有序}
        \STATE 排序结束
        \ELSE
        \STATE 对子序列分别排序。
        \ENDIF
        \ENDWHILE
    \end{algorithmic}
\end{algorithm}
轴值的选择，尽可能使L和R长度相等。选择的方案：选择最左边的记录，随机选择和选择平均值。
快速排序的算法框架:
\begin{cpp}
    template <class Record>
    void QuickSort(Record Array[], int left, int right) {
            // Array[]为待排序数组,left,right分别为数组两端
            if (right <= left)// 只有0或1个记录,就不需排序
            return;
            int pivot = SelectPivot(left, right); // 选择轴值
            swap(Array, pivot, right);// 轴值放到数组末端
            pivot = Partition(Array, left, right); // 分割后轴值正确
            QuickSort(Array, left, pivot-1);// 右子序列递归快排
            QuickSort(Array, pivot +1, right);// 右子序列递归快排
        }
    int SelectPivot(int left, int right) {
            // 选择轴值,参数left,right分别表示序列的左右端下标
            return (left+right)/2;// 选中间记录作为轴值
        }
\end{cpp}
分割函数：
\begin{cpp}
    int Partition(Record Array[], int left, int right) {
    // 分割函数,分割后轴值已到达正确位置
    int l = left;// l 为左指针
    int r = right;// r 为右指针
    Record TempRecord = Array[r];// 保存轴值
    while (l != r) {// l, r 不断向中间移动,直到相遇
            // l 指针向右移动,直到找到一个大于轴值的记录
            while (Array[l] <= TempRecord && r > l)
            l++;
            if (l < r) {// 未相遇,将逆置元素换到右边空位
                    Array[r] = Array[l];
                    r--;// r 指针向左移动一步

                }
            // r 指针向左移动,直到找到一个大于轴值的记录
            while (Array[r] >= TempRecord && r > l)
            r--;
            if (l < r) {// 未相遇,将逆置元素换到左空位
                    Array[l] = Array[r];
                    l++;// l 指针向右移动一步
                }
        } //end while
    Array[l] = TempRecord; // 把轴值回填到分界位置 l 上
    return l;// 返回分界位置l
\end{cpp}
时间代价，长度为n的序列，时间为T(n),选择轴的时间为常数，分割时间为cn,分割后长度分别为i和n-i-1。左右子序列T(i)和T(n-i-1)，递推方程$T(n) = T(i)+T(n-i-1)+cb$,总时间代价为:$T(n)=T(1)+c\sum_{i=2}^ni=\Theta(n^2)$。最佳情况下$T(n)=2T(n/2)+cn=cnlogn+n=\Theta(nlogn)$，等概率情况下，轴值数组分成长度为0和n-1,1和n-2,子序列的概率相等，都为1/n。$T(n)=\Theta(nlogn)$
\begin{example}[一种版本的快排实现]
    将待排序的数组左边的第一个元素作为privot，使用索引i从左到右，j从右到左分别找到大于基准，小于基准的两个数，交换其值，直到i=j,这时候的这个位置为基准应该待的位置，于是将基准值和这个值交换。一遍排序完成。接下来递归的排序，left到i-1和i+1到right。反复直到left<=right。排序过程如\figref{fig:fastsort_process}：
    \begin{figure}[H]
        \includegraphics[width=0.5\textwidth]{fastsort_process}
        \caption{快速排序过程}
        \label{fig:fastsort_process}
    \end{figure}
\end{example}
\cppfile[firstline=1,lastline=22]{code/arith/ex33/main.cpp}
\begin{example}[随机轴值的快速排序]
\end{example}
\cppfile[firstline=1,lastline=30]{code/arith/ex14/main.cpp}
\subsection{插入排序}
插入排序：将每一张牌插入已排序的数组中的适当位置，排序过程如下：
\begin{enumerate}
    \item 从数组中第二个元素开始抽取元素。
    \item 把它和左边第一个元素比较，如果左边第一个元素比它大，则继续与左边第二个元素比较下去直到遇到比它小的元素放在该元素的后面。
    \item 反复执行步骤2，直到结束。
\end{enumerate}
\begin{itemize}
    \item 时间复杂度：$O(n^2)$
    \item 空间复杂度：$O(1)$
    \item 稳定排序
    \item 原地排序
\end{itemize}
\begin{algorithm}
    \caption{插入排序算法}
    \label{al:al2}
    \begin{algorithmic}
        \STATE 数组长度为n，索引下标为1
        \WHILE{下标不等于n-1}
        \STATE 比较索引所在元素和之前的元素
        \IF{大于前一个元素。}
        \STATE 则该元素放在前一个元素后面，索引+1。
        \ELSIF{大于某一个元素小于另一个元素。}
        \STATE 插入到两个数之间，索引+1。
        \ELSE
        \STATE 插入到第一个元素之前，索引+1。
        \ENDIF
        \ENDWHILE
    \end{algorithmic}
\end{algorithm}
\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{insert_sort}
    \caption{插入排序算法过程}
\end{figure}
\textbf{代码实现：}
\cppfile[firstline=3,lastline=17]{code/arith/sort/main.cpp}
\begin{itemize}
    \item 该算法稳定。
    \item 空间代价$\Theta$（因为分配空间存储临时的值temp用来交换)
    \item 时间代价：
          \begin{itemize}
              \item 最佳情况：n-1此比较，2(n-1)（每个元素线移动到临时变量temp，之后移到对应位置）次移动，
              \item 最差情况：$\Theta(n^2)$
                    \begin{itemize}
                        \item 比较1~n-1个，共$\frac{n(n-1)}{2}=\Theta(n^2)$
                        \item 移动次数：$\sum_{i=1}^{n-1}(i+2)=(n-1)(n+4)/2=\Theta(n^2)$(第i个元素一出一进2此，前面的元素移动i次，总共i+2次)
                    \end{itemize}
              \item 平均情况$\Theta(n^2)$

          \end{itemize}
\end{itemize}
插入排序最好情况下时间代价$\Theta(n)$,对于短序列比较有效。
\subsection{冒泡排序}
将待排序数组的第一个元素和后一个元素比较，如果大于后一个元素，则交换两个元素的位置。接着比较第二个元素和第三个元素同样的方式比较到倒数第二个元素。一次比较完成，最大值在最右边。接着执行同样的操作到道速第三个直到第二个元素。
\begin{itemize}
    \item 时间复杂度：$O(n^2)$
    \item 空间复杂度：$O(1)$
    \item 稳定排序
    \item 原地排序
\end{itemize}
\cppfile{code/arith/ex97/include/bubble_sort.cpp}
\subsection{Shell排序}
Shell排序是插入排序的变种。无论是插入排序还是冒泡排序，如果数组的最大值就在第一位，要将它挪到正确的位置就需要n-1次移动。也就是说原数组的一个元素如果距离它正确的位置很远的话，则需要相邻元素交换很多次才能达到正确的位置。Shell排序就是为了加快速度改进的插入排序，交换不相邻的元素对数组局部排序。Shell排序的思想史采用插入排序的方法，先让数组中任意间隔为h的元素有序，刚开始h的大小可以使h=n/2接着让h=n/4让h一直缩小，当h=1的时候，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的。
\begin{itemize}
    \item 时间复杂度$O(nlog(n))$
    \item 空间复杂度$O(1)$
    \item 非稳定排序
    \item 原地排序
\end{itemize}
\begin{algorithm}
    \caption{Shell排序算法}
    \label{al:al3}
    \begin{algorithmic}
        \WHILE{跨度n/2}
        \IF{跨度!=1}
        \STATE 以跨度为n/2两两交换对应位置的逆序数。
        \ELSE
        \STATE 以跨度为1插入排序后跳出。
        \ENDIF
        \ENDWHILE
    \end{algorithmic}
\end{algorithm}
\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{shell_sort.pdf}
    \caption{Shell排序过程}
\end{figure}
\textbf{代码}
\cppfile[firstline=19,lastline=59]{code/arith/sort/main.cpp}
算法分析：
\begin{itemize}
    \item 不稳定
    \item 空间代价$\Theta(1)$
    \item 时间代价
          \begin{itemize}
              \item 增量每次除以2,$\Theta(n^2)$
              \item 选择适当的增量学列可以使得时间代价接近$\Theta(n)$
          \end{itemize}
\end{itemize}
\subsection{堆排序}
\begin{definition}[堆]
    堆是一种树形结构，它的节点比两个字节点都大。知道某一个节点k,左节点为2k,又节点为2k+1,知道节点k，其父节点为k/2。（数组表示的堆）
\end{definition}
堆排序需要做事：
\begin{itemize}
    \item 构建最大堆。
    \item 将最大堆的根节点和最后一个元素交换，然后构造最大堆。
    \item 将倒数第二个元素和最大堆根节点交换，反复直到结束。
\end{itemize}
最大堆调整过程：
\begin{itemize}
    \item 找到最后一个非叶子节点作为根节点。
    \item 如果这个节点存在左节点则对比根节点和左节点的值，找到值更大的索引作为最大节点。
    \item 如果右节点存在，则对比右节点和上面找到的最大节点，更新最大节点。
    \item 如果最大节点不是此根节点，则交换根节点和最大节点，然后对当前最大节点递归调用此算法。
\end{itemize}
初始化最大堆如\figref{fig:heap_init}：
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{heap_init}
    \caption{最大堆的初始化}
    \label{fig:heap_init}
\end{figure}
\cppfile[firstline=1,lastline=14]{code/algorithm/src/heap.cpp}
最大堆构建过程如\figref{fig:buildheap}：
\begin{itemize}
    \item 从最大堆的最后一个非叶子节点开始往前遍历，直到整个堆的根，对于每个节点，使用上述调整算法调整。
\end{itemize}
\cppfile[firstline=15,lastline=20]{code/algorithm/src/heap.cpp}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{buildheap}
    \caption{最大堆的构建}
    \label{fig:buildheap}
\end{figure}
\cppfile[firstline=21,lastline=32]{code/algorithm/src/heap.cpp}
\cppfile{code/offer/ex9/main.cpp}
\subsection{归并排序}
先划分，再归并。
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{mergesort_process}
    \caption{归并排序}
\end{figure}
\cppfile{code/arith/ex39/main.cpp}
\subsection{桶排序}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=\textwidth]{bucketsort}
    \caption{桶排序}
    \label{fig:bucketsort}
\end{figure}
假设排序数据服从[0-1)的均匀分布。然后对于[0-0.1)、[0.1-0.2)、……，[0.9-1)的10个桶，将属于各自区间的元素放入桶中，放入的时候按照顺序放置。然后遍历整个桶，将里面的元素分别取出拼接为最终数组。排序流程如\figref{fig:bucketsort}
\cppfile{code/algorithm/src/bucketsort.cpp}
性能分析：数组长度为n，所有记录区减[0,m),时间代价为：统计桶的数量需要遍历数组代价为$\Theta(n)$,累加桶需要对桶的前m个元素求和，代价为$\Theta(m)$，总的时间代价为$\Theta(n+m)$,空间代价：需要m个计数器（记录元素次数）和长度为n的临时数组（排序存放的数组）。$\Theta(m+n)$。算法稳定。该算法适用于：\textcolor{red}{m相对于n很小的情况。否则桶的统计代价就很大。}
\subsection{计数排序}
对于待排序数组中的元素a，使用[0-max(a)]的中的元素填充的数组c。通过c纪录数组a中每个元素出现的频率，因为存在同一个元素出现两次的情形。对于数组c中的元素再次求以纪录小于index的元素有多少个。然后 b 为排序之后的数组，从后向前遍历数组 a，找到b[a[i]] = a[i]（小于a[i]的元素个数为b[a[i]]，a[i]应该放于此）。这时候 a[i] 已经放到了正确的位置，所以更新 c[a[i]] = c[a[i]]-1。
\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{counter_sort}
    \caption{计数排序流程}
    \label{fig:counter_sort}
\end{figure}
这里需要说明的是计算小于n的元素的个数，算法通过统计元素出现的次数，然后累计求和实现 $O(n)$ 完成。
\cppfile{code/algorithm/src/countSort.cpp}
\section{树算法}
\subsection{判断子树在不在另一棵树上面}
\emph{约定空树不是任意一个树的子结构}
\begin{example}[判断树是否包含另一棵子树]
    \begin{figure}[H]
        \centering
        \includegraphics[width=\textwidth]{isSubStructure}
        \caption{判断子树是不是树的一部分}
        \label{fig:isSubStructure}
    \end{figure}
\end{example}
\begin{itemize}
    \item 子树为空，根据约定判断返回false。
    \item 树为空，空树不包含任何子树，返回false。
    \item 如果树和子树都不为空，根据根节点判断子树是否相同。
          \begin{itemize}
              \item 子树相同：返回true。
              \item 子树不同:则说明和子树相同的节点可能并非当前根节点，选择其左右节点分别递归调用，两则有一个为true则结果为true。
          \end{itemize}
\end{itemize}
\cppfile[firstline=2,lastline=21]{third_party/coding/cxx/algorithm/src/isSubStructure.cpp}
\subsection{树的镜像}
\begin{example}
    树的镜像：
    \begin{figure}[H]
        \centering
        \includegraphics[width=\textwidth]{mirror_tree}
        \caption{树的镜像}
    \end{figure}
\end{example}
对于根节点的左孩子保存起来，左孩子指向右孩子的mirror（如果直接指向右孩子会出现右孩子的子节点没有镜像）。这时候将右节点指向保存的左孩子mirror，最后返回根节点。
\cppfile[firstline=2,lastline=14]{third_party/coding/cxx/algorithm/src/mirrorTree.cpp}
深度优先搜索实现：深度优先搜索每个节点，对每个节点的左右子节点交换。最后返回根节点
\cppfile[firstline=15,lastline=39]{third_party/coding/cxx/algorithm/src/mirrorTree.cpp}
\subsection{判断二叉树是不是对称二叉树}
\begin{example}[判断二叉树是是对称二叉树]
    \begin{figure}[H]
        \centering
        \includegraphics[width=0.5\textwidth]{sym_tree}
        \caption{对称二叉树}
        \label{fig:sym_tree}
    \end{figure}
\end{example}
\begin{Mind}{判断对称二叉树}{}
    假设两棵完全相同的树分别遍历两棵树，中序遍历（根左右），先对比根节点，如果根节点不为空且值相同，我们递归对比a树的左节点和b数的右节点与b树的左节点于a树的右节点。
\end{Mind}
\cppfile[firstline=1,lastline=18]{third_party/coding/cxx/algorithm/src/isSymmetric.cpp}
\subsection{判断二叉搜索树}
\begin{example}
    判断一棵树是否为二叉搜索树（BST，左节点均比根节点小，右节点均比根节点大）。
\end{example}
\begin{Mind}{判断二叉搜索树思路}{}
    如果树的根节点为空，则树是二叉搜索树。否则需要根据二叉搜索树规则判断判断。递归调用的时候传入最小值和最大值，分别用根节点的值何其比较，不满足则不为二叉搜索树，否则左右子树节点分别比较。比较左子树的时候需要确保其值比上一个根节点小，所以上界为上一个根节点，右节点类似。
\end{Mind}
\cppfile[firstline=20,lastline=32]{third_party/coding/cxx/algorithm/src/isValidBST.cpp}

%\subsection{分层打印每一层的元素}
%\begin{example}
%    分层打印每一行的元素的时候需要记录下当前层节点的数量，打印完节点后输出换行。
%\begin{figure}[H]
%\centering
%\includegraphics[width=0.5\textwidth]{bfs_layer}
%\caption{分层打印}
%\end{figure}
%\end{example}
%\cppfile[firstline=15,lastline=48]{code/arith/ex28/main.cpp}
\subsection{二叉树的深度}
\begin{example}[二叉树最大深度]
    如果节点是根节点，深度为1,如果节点只有子树，深度为左子树节点+1，如果是只有右子树，深度是右子树+1,如果两者都有，深度为左右子树深度的最大值。
    \begin{figure}[H]
        \centering
        \includegraphics[width=0.4\textwidth]{tree_depth}
        \caption{树的深度}
    \end{figure}
\end{example}
\cppfile[firstline=2,lastline=8]{third_party/coding/cxx/algorithm/src/maxDepth.cpp}
\subsection{根节点到子节点最短距离}
\begin{example}[美团2018笔试]
    给定输入节点n，节点之间的关系，求从根节点到各个子节点的最短路径。例如：
    \begin{figure}[H]
        \centering
        \includegraphics[width=0.5\textwidth]{shortestDis}
        \caption{最短距离}
        \label{fig:meituan_1}
    \end{figure}
    \figref{fig:meituan_1} 输出最大短路径为1-2-1-3-4-3-5-6,最短路径长度为7.
\end{example}
\begin{Mind}{树的最小深度}{}
    最短路径长度为边的数目减去最大边长，即短路径走重复，长路径不走重复，最短路径为总边的2倍减去最大路径（$2*(Node-1)-maxpath$）。代码实现用一个传入参数记录当前访问到for循环结束后的边数，防止了递归调用中该变量被初始化。改变其值。
\end{Mind}
\cppfile[firstline=1,lastline=42]{code/offer/meituan/main.cpp}
\subsection{将有序数组转化为二叉树}
\begin{example}[将有序数组转化为二叉树]
    将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。示例:
    给定有序数组: [-10,-3,0,5,9],一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
    \begin{Textcode}
        0
        / \
        -3   9
        /   /
        -10  5
    \end{Textcode}
\end{example}
\begin{Mind}{转化数组为二叉树}{}
    获取数组的中间元素作为树的根节点，对于左右元素。将左右元素作为递归调用的节点，返回树的根节点。
\end{Mind}
\cppfile[firstline=2,lastline=18]{third_party/coding/cxx/algorithm/src/sortedArrayToBST.cpp}
\subsection{重建二叉树}
\begin{example}{重建二叉树}
    输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和终须遍历的结果都不包含重复数字。例如，输入前序遍历序列[1,2,4,7,3,5,6,8]和中序遍历列表[4,7,2,1,5,3,8]，则重建如\figref{fig:rebuild_tree}的二叉树并输出它的头节点。
\end{example}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{rebuild_tree}
    \caption{重建的二叉树}
    \label{fig:rebuild_tree}
\end{figure}
\begin{Mind}{重建二叉树思路}{}
    \figref{fig:tree_array}前序遍历的第一个元素为树的根节点，中序遍历根节点左右分别为子树。
\end{Mind}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{tree_array}
    \caption{前序和中序遍历序列}
    \label{fig:tree_array}
\end{figure}
\cppfile[firstline=7,lastline=27]{third_party/coding/cxx/algorithm/src/reConstructBinaryTree.cpp}
\subsection{二叉树的右视图}
\begin{Textcode}
    请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图
    示例1
    [1,2,4,5,6,3],[5,4,6,2,1,3]
    返回值
    [1,3,4,6]
\end{Textcode}
\begin{Mind}{二叉树的右视图}{}
    重建二叉树，BFS存储每一层的节点，将每一层的节点的最后一个节点存放进数组。
\end{Mind}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=.5\textwidth]{TreeLeftView}
    \caption{右视图}
\end{figure}
\cppfile[firstline=6,lastline=39]{third_party/coding/cxx/algorithm/src/treeRightView.cpp}
\subsection{之字型打印二叉树}
第一层从左往右打印，第二层从右往左打印，以此类推。
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{pos_neg_tree}
    \caption{之字型打印}
\end{figure}
\begin{Mind}{之字型打印}
    如\figref{fig:zhitravel}使用两个栈，奇数偶数栈先放左节点然后放右节点，偶数栈反之。
\end{Mind}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=.5\textwidth]{zhitravel}
    \caption{之字遍历}
    \label{fig:zhitravel}
\end{figure}
\cppfile[firstline=5,lastline=48]{third_party/coding/cxx/algorithm/src/zigzagLevelOrder.cpp}
\subsection{是否为平衡二叉树}
平衡二叉树\textcolor{red}{每个节点}是指二叉树的左右子树的高度差。
\begin{Mind}{平衡二叉树}
    对根节点判断左右子树高度差是否$<=1$，如果是则对其左右子节点分别递归判断。直到碰到叶子节点（左右子节点为空），返回 true 。
\end{Mind}
\subsection{在树中寻找和为指定值的路径打印出来}
\begin{example}[在树中寻找和为指定值的路径]
    \begin{figure}[H]
        \centering
        \includegraphics[width=0.3\textwidth]{find_path}
        \caption{树}
        \label{fig:find_path}
    \end{figure}
    如\figref{fig:find_path}树中和为22的路径有10-5-7和10-12。输出结果如下：
    \begin{Textcode}
        10 5 7
        10 12
    \end{Textcode}
\end{example}
\begin{Mind}{算法思路}{}
    如果节点不为空，取出节点的值，然后看其左右子树是不是叶子节点。如果是的话以左右子树作为当前节点递归调用。当到达叶子节点同时和不为指定值说明叶子节点不合适，删除叶子节点的值。否则当到达叶子节点并且和为指定值的时候输出路径。
\end{Mind}
\cppfile[firstline=6,lastline=24]{third_party/coding/cxx/algorithm/src/pathSum.cpp}
\section{遍历数据结构}
\subsection{先序遍历}
\emph{先序遍历：先遍历根节点，然后左节点最后右节点。}
\begin{figure}[H]
    \centering
    \includegraphics[width=.5\textwidth]{posTraval}
    \caption{先序遍历[3,9,4,5,7]}
    \label{fig:preTraval}
\end{figure}
\cppfile[firstline=2,lastline=20]{third_party/coding/cxx/algorithm/src/preorderTraversal.cpp}
\subsection{后序遍历}
\emph{后序遍历：先遍历左节点，然后右节点最后根节点。}
\begin{figure}[H]
    \centering
    \includegraphics[width=.5\textwidth]{posTraval}
    \caption{后序遍历[9,5,7,4,3]}
    \label{fig:posTraval}
\end{figure}
递归版后序遍历：
\cppfile[firstline=2,lastline=18]{third_party/coding/cxx/algorithm/src/postorderTraversal.cpp}
\subsection{中序遍历}
\emph{中序遍历：先遍历左节点，然后根节点最后右节点。}
\begin{figure}[H]
    \centering
    \includegraphics[width=.5\textwidth]{posTraval}
    \caption{中序遍历[9,3,5,4,7]}
    \label{fig:inTraval}
\end{figure}
\cppfile[firstline=5,lastline=20]{third_party/coding/cxx/algorithm/src/inorderTraversal.cpp}
\subsection{BFS}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.3\textwidth]{bfs_tree}
    \caption{树的BFS遍历}
    \label{fig:bfs_tree}
\end{figure}
\subsubsection{BFS非递归实现}
\begin{example}[实现宽度优先搜索遍历]
    \begin{figure}[H]
        \centering
        \includegraphics[width=0.5\textwidth]{bfs_travel}
        \caption{宽度优先搜索}
    \end{figure}
\end{example}
\cppfile[firstline=2,lastline=28]{third_party/coding/cxx/algorithm/src/BFSTravel.cpp}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{bfs_tree_queue}
    \caption{树的BFS遍历（非递归）}
    \label{fig:bfs_tree_queue}
\end{figure}
BFS的非递归处理：
\emph{如果根节点不为空将根节点加入队列，然后如果队列不为空则节点出队，拿到节点的值然后将节点的左右子节点（不为空）加入队列，直到队列为空为止}。
\subsection{DFS}
DFS搜索函数的重要组成部分：
\begin{itemize}
    \item 节点（递归调用的时候使用不同的节点递归访问）
    \item 是否访问(告诉函数某一个节点是否访问)
    \item 搜索图（这个图不一定是真正的图，可以是二维的邻接矩阵，也可以是邻接表等，图在代码中不会变动）
\end{itemize}
DFS通常用来遍历整个图或者树，但是使用DFS的目的通常为了通过遍历所有可能性求出需要了解的节点组合或者最小路径长度之类的结果，所以调用DFS后处理才是问题的关键。DFS递归调用结束表示给定节点能访问的可能性都访问完了，如果是为了获取图的可访问数目，这时候只需要添加计数即可找到所有能访问的节点组合。DFS实现有两种方式：
\begin{enumerate}
    \item 递归方式。
    \item 非递归方式。
\end{enumerate}
对于\figref{fig:dfs_tree}的树：
\begin{figure}[H]
    \centering
    \includegraphics[width=0.3\textwidth]{dfs_tree}
    \caption{树的DFS遍历（递归）}
    \label{fig:dfs_tree}
\end{figure}
递归方式遍历整棵树的流程：访问根节点（1），如果根节点不为空递归访问根节点的左节点和右节点，直到节点左右子节点为空为止。非递归方式流程如\figref{fig:dfs_tree_stack}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.8\textwidth]{dfs_tree_stack}
    \caption{树的DFS遍历（非递归）}
    \label{fig:dfs_tree_stack}
\end{figure}
非递归访问方式：
\begin{enumerate}
    \item 如果根节点不为空，将根节点入栈。
    \item 出栈，遍历节点内容。同时将当前节点的右节点和左节点入栈。
\end{enumerate}
DFS非递归方式访问模板：
\begin{cpp}
    boolean DFS(int root,int target){
            set<Node> visitor;//当前节点是否访问过
            stack<Node> s;
            s.add(root);//根节点入栈
            while(!s.empty()){
                    Node current = s.top();//获取栈顶节点
                    if(current == target)//这里的条件根据具体访问有所不同
                    return true;
                    for(auto current_node:current_nodes){//current_nodes为current连接的节点列表
                            if(visitor.count(current_node)!=0){// 如果节点列表中的节点没有被访问过
                                    s.push(current_node);//将节点入栈
                                    visitor.add(current_node);//标记当前节点已经访问过
                                }
                        }
                    s.pop(current);
                }
            return false;
        }
\end{cpp}
\subsubsection{二叉树层序遍历}
\begin{example}
    给你一个二叉树，请你返回其按层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。示例：二叉树：[3,9,20,null,null,15,7],
\end{example}
\begin{Textcode}
    3
    / \
    9  20
    /  \
    15   7
    返回其层次遍历结果：
    [
    [3],
    [9,20],
    [15,7]
    ]
\end{Textcode}
\subsubsection*{BFS非递归实现}
这个任务本质上是需要分层打印二叉树的每一层的节点，不同在于每一层需要单独打印而不是将BFS结果打印。这里的关键是需要记录进入队列的元素个数，比如3进去队列，此时元素只有一个。将这一层的一个元素存在vector里面。第二层的时候9和20都需要进入队列，此时元素个数为2个，这层元素为两个。通过for循环每次出队的时候将当前层的元素取出（不同于直接BFS一般是while循环）。
\cppfile[firstline=6,lastline=33]{third_party/coding/cxx/algorithm/src/levelOrder.cpp}
\subsubsection*{DFS实现层序遍历}
使用DFS，DFS可以通过层递归。例如根节点3属于第0层，需要一个vector<int>存储0层的元素，因为没法预先知道树有多少层，所以只能通过层添加存储当前层元素的vector到最后的结果中。然后对于当前节点，将其中的值放入层vector。之后分别遍历当前节点的下一层节点。这样当访问到根节点5之后左右节点都为空，退回到节点2,访问2的右节点。因为我们通过层获取result中这一层的vector，所以这一层的另一个元素6也会被添加这一层中，反复递归调用直至结束。
\cppfile[firstline=34,lastline=51]{third_party/coding/cxx/algorithm/src/levelOrder.cpp}
\section{回溯}
在r行c列的格子阵列中查找能走过的格子，要求格子坐标的x，y的位数和小于指定的threshold。(例如，c=5,r=5,threshold=18,能访问25个格子数)。这里需要注意的是事实上不需要上下左右的寻找，\figref{fig:robot}因为机器人的起点不可能一开始就在网格中间[2,3]，只有在网格中间遍历所有网格的时候才需要上下左右，而从左上角[0,0]通过向下或者向右走即可走完所有的网格，走到网格中间的过程中此网格的上面和左面已经走过，所以只需要考虑从每个网格往下和往右边走即可。
\begin{figure}[H]
    \centering
    \includegraphics[width=.5\textwidth]{robot}
    \caption{[2,3]为起点搜索}
    \label{fig:robot}
\end{figure}
\cppfile[firstline=2,lastline=43]{third_party/coding/cxx/algorithm/src/movingCount.cpp}
\subsection{朋友圈问题}
\begin{example}
    班上有 N 名学生。其中有些人是朋友，有些则不是。它们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。给定一个 $N \times N$ 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
    \textbf{示例：}
    \begin{Textcode}
        输入:
        [[1,1,0],
        [1,1,0],
        [0,0,1]]
        输出: 2
        说明：已知学生0和学生1互为朋友，它们在一个朋友圈。
        第2个学生自己在一个朋友圈。所以返回2。
    \end{Textcode}
    \textbf{注意：}
    \begin{itemize}
        \item N 在[1,200]的范围内。
        \item 对于所有学生，有M[i][i] = 1。
        \item 如果有M[i][j] = 1，则有M[j][i] = 1。
    \end{itemize}
\end{example}
\cppfile[firstline=1,lastline=44]{code/offer/ex4/main.cpp}
\begin{remark}
    在这段代码中我们没有按照上面提出的添加DFS三参数(图，visited，访问节点)，因为在类中我们已经将图和visited加入，加入的目的也是为了不同函数能共享数据而不是每次写三个参数调用。
\end{remark}
\begin{example}
    输入数字n，m，在1-m之间找出数使得它们的和等于m。
\end{example}
下面以m=n=5为例子说明：
任务是在1-5之间找到能求和得到5的数字，假设我们找到了1,那剩下的任务是在2-5之间找到数组使得和为4。假设选择2,剩下的任务是在3-5之间选择求和结果为2的数，但是明显没有这样的结果，于是2是不合适的，出栈。3进栈，接下来的任务是在3-5之间选择数使得能求和等于1,显然也不满足条件，出栈，3入站，剩下的任务是在接下来的任务是在0个可选的值中选择数，于是直接输出结果。接下来2入栈，剩下的任务是从3-5中选择能得到3的数，于是选中3,接下来是3入栈，剩下的任务是在4-5中选择2,不可能，于是3出栈，4也是这样直到结束。
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{dfs1}
    \caption{dfs示意图}
\end{figure}
\cppfile[firstline=1,lastline=17]{code/arith/ex13/main.cpp}
\section{图算法}
\subsection{拓扑排序}
拓扑排序用于在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：
\begin{itemize}
    \item 每个顶点出现且只出现一次。
    \item 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
\end{itemize}
有向无环图（DAG）才有拓扑排序。排序流程：找到入度为0（只能从该节点出不能有进）的点。删除其相连的边，然后对剩下的节点做同样的操作直到之后一个节点停止。示意图如\figref{fig:toposort}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{toposort}
    \caption{拓扑排序流程}
    \label{fig:toposort}
\end{figure}
\subsection{排课问题}
\begin{Textcode}
    现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

    示例 1:

    输入: 4, [[1,0],[2,0],[3,1],[3,2]]
    输出: [0,1,2,3] or [0,2,1,3]
    解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。 因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
\end{Textcode}
\begin{itemize}
    \item 通过课程关系构建邻接表。
    \item 从邻接表起点开始一个个查找节点，找绕节点后将此节点标记为正在访问（数值0表示没有访问、数值1表示正在访问、数值2表示已经访问过了）。
    \item 访问到某一个节点的时候分为以下几种情况：
          \begin{enumerate}
              \item 当前节点没有被访问，以此节点作为下一个节点继续访问。
              \item  当前节点为正在访问，说明访问的时候已经碰到了环。这时设置标记，有环，则无需继续访问了。
              \item 当前节点没有可访问节点了。设置此节点状态为2同时将此节点放入堆栈。
          \end{enumerate}
    \item 如果没有环则返回栈反序之后的结果否则为空向量。
\end{itemize}
算法示意图如\figref{fig:dfs_topo}：
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=\textwidth]{dfs_topo}
    \caption{基于DFS的排序流程}
    \label{fig:dfs_topo}
\end{figure}
\cppfile[firstline=7,lastline=48]{code/datastruct/graph/src/findOrder.cpp}
时间复杂度: $O(n+m)$其中 $n$ 为课程数，$m$ 为先修课程的要求数。这其实就是对图进行深度优先搜索的时间复杂度。

空间复杂度: $O(n+m)$。题目中是以列表形式给出的先修课程关系，为了对图进行深度优先搜索，我们需要存储成邻接表的形式，空间复杂度为 $O(n+m)$。在深度优先搜索的过程中，我们需要最多 $O(n)$ 的栈空间（递归）进行深度优先搜索，并且还需要若干个 $O(n)$ 的空间存储节点状态、最终答案等。

使用广度优先排序算法：

我们使用一个队列来进行广度优先搜索。开始时，所有入度为 0 的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且它们之间的相对顺序是无关紧要的。在广度优先搜索的每一步中，我们取出队首的节点 head：
\begin{enumerate}
    \item 我们将 $head$ 放入答案中；
    \item 我们移除 $head$ 的所有出边，也就是将 $head$ 的所有相邻节点的入度减少 1。如果某个相邻节点 next 的入度变为 0，那么我们就将 next 放入队列中。
\end{enumerate}
在广度优先搜索的过程结束后。如果答案中包含了这 $next$ 个节点，那么我们就找到了一种拓扑排序，否则说明图中存在环，也就不存在拓扑排序了。算法流程如下\figref{fig:bfs_topo}：
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=\textwidth]{bfs_top}
    \caption{bfs实现}
    \label{fig:bfs_top}
\end{figure}

\cppfile[firstline=42,lastline=76]{code/datastruct/graph/src/findOrder.cpp}
时间复杂度: $O(n+m)$，其中 $n$ 为课程数，$m$ 为先修课程的要求数。这其实就是对图进行广度优先搜索的时间复杂度。

空间复杂度: $O(n+m)$。题目中是以列表形式给出的先修课程关系，为了对图进行广度优先搜索，我们需要存储成邻接表的形式，空间复杂度为 $O(n+m)$。在广度优先搜索的过程中，我们需要最多 $O(n)$ 的队列空间（迭代）进行广度优先搜索，并且还需要若干个 $O(n)$ 的空间存储节点入度、最终答案等。
\subsection{有向无环图的最大路径}
拓扑排序加上动态规划。设maxDepth[v]表示从源点到节点v的最大路径，则 maxDepth[v] = max(maxPath[v]，maxPath[k]+e[k][v])。即到v的最大路径值为到与v相邻的节点k的最大值找到后，由k到v的路径中最大值。
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.8\textwidth]{longestPath}
    \caption{最长路径}
    \label{fig:longestPath}
\end{figure}
如\figref{fig:longestPath}，求到达点D的最长路径maxPath[D]。假设maxPath[B]和maxPath[C]已经得到了，那么到达D的最大路径 maxPath[D] = max(maxPath[B]+1,maxPath[c]+3)。
\subsection{Prim算法}
\subsection{Kruscal算法}
\begin{remark}
    \begin{enumerate}
        \item 取出所有的边。
              \begin{enumerate}
                  \item 找到算法结束条件
                  \item 从边集合中找到最小边。
                  \item 找出点所在的点集合。
                  \item 根据点所在集合的不同做出不同处理。
              \end{enumerate}
    \end{enumerate}
\end{remark}
\subsection{卡特兰数}
卡特兰数是一组数，数字形式为${1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862}$。
我们从一个简单的题目了解卡特兰数。
\begin{example}{栈的出栈序列}

    n个元素进栈顺序为$1,2,3,\ldots,n$，出栈有多少序列？
\end{example}
我们将进栈表示为+1,出栈表示为-1.出栈序列为1,3,2可以用如下\figref{fig:stack_in_out}表示：
\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{stack_in_out.pdf}
    \caption{出入栈顺序}
    \label{fig:stack_in_out}
\end{figure}
根据栈本身的特点，每次出栈必须要有元素在栈中。这样就有合法出栈顺序的对应序列的任意子序列(从头开始)的前缀和都是大于等于0的。比如上面的合法出栈序列$+1,-1,+1,+1,-1,-1$，对于只有三个元素的出栈序列$+1,-1,-1,+1,-1,+1$序列的前三项和小于0,说明此出栈序列不合法。如果第一个前缀和小于0的前缀的三个元素取反，就可以得到序列$-1,+1,+1,+1,-1,+1$，此时序列有3+1个+1（入栈）和3-1个-1（出栈）。因为这个小于0的前缀和必然是-1（还没达到-1的时候就已经是第一个前缀和小于0的前缀）。此序列中的-1比+1多一个，反转后+1比-1多一个。即对于n个元素的每种非法出栈序列都会对应一个含有n+1和+1和n-1个-1的序列。这里需要说明的是合法不合法序列需要保证-1和+1的个数相等且等于入栈元素个数n。例如：$-1,-1,-1,-1,-1,-1$是不合法出栈序列，但是不符合要求。假设非法序列为 A，对应的序列为 B。每个 A 只有一个"第一个前缀和小于 0 的前缀"，所以每个 A 只能产生一个 B。而每个 B 想要还原到 A，就需要找到"第一个前缀和大于 0 的前缀"，显然 B 也只能产生一个 A。
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{stack_sequence}
    \caption{两种序列唯一对应}
    \label{fig:stack_sequence}
\end{figure}
每个B都有n+1个+1和n-1个-1.因此B的数量为$C_{2n}^{n+1}$，相当与在长度为2n的序列中找到n+1个位置存放+1.相应的，非法序列的数量就等于$C_{2n}^{n+1}$。出栈序列的总数量总共有$C_{2n}^n$，因此，合法的出栈序列的数量为$C_{2n}^n-C_{2n}^{n+1}=\frac{C_{2n}^{n}}{n+1}$，因此我们就的到了卡特兰数的通项公式$\frac{C_{2n}^n}{n+1}$。
\begin{cpp}
    double catalan(int n) {
            double temp = 0;
            if (n == 0 ||n ==1)
            temp = 1;
            else
            temp = catalan(n - 1) * (4 * n - 2) / (n + 1);
            return temp;
        }
\end{cpp}
\subsubsection{卡特兰树问题}
\begin{example}{满二叉树的组合数}
    n+1个叶子节点能够组成多少中形状不同的满二叉树（每个节点如果有叶子节点则左右叶子节点都有）。
\end{example}
\subsubsection*{思路}
使用深度优先搜索这个满二叉树，向左扩展时标记为 +1，向右扩展时标记为 -1。由于每个非叶子节点都有两个左右子节点，所有它必然会先向左扩展，再向右扩展。总体下来，
左右扩展将会形成匹配，即变成进出栈的题型。n + 1 个叶子结点会有 2n 次扩展，构成$\frac{C_{2n}^{n}}{n+1}$种形状不同的满二叉树。
\begin{example}{电影购票}

    电影票一张 50 coin，且售票厅没有 coin。m 个人各自持有 50 coin，n 个人各自持有 100 coin。
    则有多少种排队方式，可以让每个人都买到电影票。
\end{example}
\subsubsection*{思路}
持有 50 coin 的人每次购票时不需要找零，并且可以帮助后面持有 100 coin 的人找零；而对于持有 100 coin 的人每次购票时需要找零，但 100 coin 对后面的找零没有任何作用。因此，相当于每个持有 100 coin 的人都需要和一个持有 50 coin 的人进行匹配。我们将持有 50 coin 的标记为 +1，持有 100 coin 的标记为 -1，此时又回到了进出栈问题。不同的是，m 不一定等于 n，且排队序列是一种排列，需要考虑先后顺序，例如各自持有 50 coin 的甲和乙的前后关系会造成两种不同的排队序列。所以，将会有$(C_{m+n}^m-C_{m+n}^{m+1})\cdot m!\cdot n!$第二项为什么是$C_{m+n}^{m+1}$ ，其实很简单，我们每次把第一个前缀小于 0 的前缀取反后，会造成 +1 多了一个而 -1 少了一个。这里 +1 有 m 个，-1 有 n 个，取反后 +1 变成 m + 1个，-1 变成 n - 1个，总和不变。
\subsubsection{卡特兰数通项计算}
卡特兰数通项公式计算：
\begin{equation}
    C_n=\begin{cases}
        C_{n-1}\frac{4\cdot n-2}{n+1}\quad n>1 \\
        1\quad n = 1
    \end{cases}
\end{equation}

需要注意的是，由于卡特兰数增长速度较快，当 n 等于 17 时，卡特兰数将会超过 int 最大值，造成溢出（Python 除外）。对于 Java 语言来说，可以使用 BigInteger 来计算大整数。那如果 +1 的数量不等于 -1 的数量呢，如前面提到的电影购票问题。此时 $C_n = C_{m+n}^{m}-C_{m+n}^{m+1}$，不是卡特兰数的通项，也就不能够继续使用原有的递推性质。直接推：
\begin{equation*}
    \begin{split}
        C_n&=C_{m+n}^m+C_{m+n}^{m+1}\\
        &=\frac{(m+n)!}{m!n!}-\frac{(m+n)!}{(m+1)!(n-1)!}\\
        &=\frac{(m+n)!}{m!n!}-\frac{(m+1)!\frac{n}{m+1}}{m!\cdot n!}\\
        &=\frac{(m+n)!}{m!\cdot n!}\cdot(1-\frac{1}{m+1}n)\\
        &=\frac{(m+n)!}{m!\cdot n!}\cdot \frac{m+1-n}{m+1}
    \end{split}
\end{equation*}
一般而言，为了降低难度，题目会要求我们计算排列数量，所以 $A_n = C_n\cdot m!\cdot n!=(m+n)!\cdot \frac{m+1-n}{m+1}$

。

\section{数组}
\subsection{数组中查找元素}
\begin{example}
    试题：在一个长度为n+1的数组中找到重复的数组，数字范围为1-n。不允许修改原始的数组。
\end{example}
\begin{Mind}{数组中查找元素}{}
    类似二分法查找的思想，如果数组数值范围为1-n,但是数组长度为n+1,说明肯定有重复数字。也就是说可以通过数值范围和数组长度判断重复数字出现的区域。假如数组为[2,3,5,4,3,2,6,7]有8（n+1）个元素。数值范围在1-7(n)之间。
    如果在1-4之间数组中的元素个数大于4，那么重复数字的范围在1-4之间，统计1-4之间出现的数的个数为5，所以重复数字在1-4之间。在1-2之间出现的元素有2,3-4出现的元素有3个。重复元素出现在3-4之间。接着对3-4之间的元素分别统计获取3出现两次，4出现一次。
    时间复杂度为：$O(nlogn)$空间复杂度为$O(1)$。
\end{Mind}
\cppfile[firstline=1,lastline=49]{code/algorithm/src/getDuplication.cpp}
\begin{remark}
    该代码存在的问题是能找到重复的数，但是不能找到所有的重复的数（比如2）。
\end{remark}
\subsection{在二维数组中查找指定的数}
算法：
在二维数组中，因为每一行都是从左向右递增，从上到下递增。从数组右上角开始，如果右上角数字大于当前数字，则此数字所在列都不用查找（必然大于目标value）于是到倒数第二列，一直找到第一列，如果等于目标value则直接返回，如果小于则对该列从上往下找，如果数字小于目标value则这一行都不需要考虑（目标左边都比value小），只能向下找，如果找到比value大，则不需查找（下面的值都比value大），找到等于的就返回。
\begin{gather*}
    \begin{bmatrix}
        1 & 2 & 8  & 9  \\
        2 & 4 & 9  & 12 \\
        4 & 7 & 10 & 13 \\
        6 & 8 & 11 & 15 \\
    \end{bmatrix}
\end{gather*}
\cppfile{code/DataStructAnd_Alg/src/findNumberIn2DArray.cpp}
\subsection{螺旋数组}
\begin{Textcode}
    给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。
    示例1
    输入
    [[1,2,3],[4,5,6],[7,8,9]]
    返回值
    [1,2,3,6,9,8,7,4,5]
\end{Textcode}
对于最外层layers=0，分别计算层起点[0,0]-[0,2]、[0,3]-[1,3]、[2,3]-[2,1]、[2,0][1,0]分别对应为：
\begin{itemize}
    \item 最外层第一段：$[layer,layer+c],c\in[0,cols-1]$
    \item 最外层第二段：$[layer+r,layer+cols-1],c\in[0,rows-1]$
    \item 最外层第三段：$[layer+rows-1,layer+c],c\in[0,cols-1]$
    \item 最外层第四段：$[layer+r,layer],c\in[0,rows-1]$
\end{itemize}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=\textwidth]{spiral}
    \caption{螺旋矩阵示意图}
\end{figure}
对于11、12两个元素，按照同样的算法，先获取左上角的一段长度为(cols-1=1)的元素，然后获取右上角到rows-1=0的元素，这时值为0，计算值漏了。所以需要将此值补上。
\cppfile{code/algorithm/src/spiralOrder.cpp}
\subsection{旋转数组中最小数字}
\begin{example}[获取旋转数组中的最小数字]
    把一个数组最开始的若干元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如\{3,4,5,1,2\}为\{1,2,3,4,5\}的一个旋转，该数组的最小值为1.
\end{example}
\begin{Mind}{查找旋转数组中的最小值}{}
    旋转数组的两部分都是有序的,一个从大到小排列的数组旋转后导致旋转后的的部分比数组最开始的元素大,所以通过二分法查找中间元素是不是大于最开始的元素如果是则逆序肯定在中点右侧,否则在中点左侧。反复缩小查找范围最后获得结果。上下指针指向同一个元素的时候这个元素就是旋转后的最小值。
\end{Mind}
\cppfile{code/ByteDance/src/findMin.cpp}
\subsection{求数组中子数组元素和最大的值}
\begin{example}[子数组中和最大的值]
    对数组从第一个元素开始往后求和，如果和小于0,加上下一个元素肯定小于下一个元素，这样最大值肯定没有从下一个元素开始求和大。这样找到只要和不为负数就累加，否则下一个数作为和的第一个数。
\end{example}
\cppfile[firstline=1,lastline=19]{code/arith/ex36/main.cpp}
\subsection{寻找数组中乘积最大结果}
\begin{example}{在无序数组中找到三个数使得乘积最大，数组中包含有正数和负数。}
\end{example}
\begin{Mind}{数组乘积最大}{}
    无序数组中既然包含正数说明正数个数至少有一个，最大数为正数。同理最小数为负数。这时候分为如下几种情况(为了方便说明，这里假设有第二大，第三大，最小，次小)：
    \begin{itemize}
        \item 如果第一个小于0的数是第二大的数，这时候第二大的数和第三大的数均为负数，判断三个数的乘积最大变成了第二大和第三大的数的乘积和最小数和次小数乘积谁更大。
        \item 如果第一个小于0的数是第三大的数，乘积最大肯定是$\text{最大数}\cdot\text{最小数}\cdot{次小数}$，因为它两都为负数乘积为正数。
        \item 如果第一个小于0的数是次小数，这时候和情况1相同，第二大数和第三大数都是正数，最小数和次小数都是负数，它两的乘积为正数。所以最大数需要判断最小数和次小数的乘积和第二大与第三大数的乘积谁更大。
        \item 如果第一个小于0的数是最小数，这时候最大乘积肯定是$\text{最大数}\cdot\text{第二大}\cdots\text{第三大}$
    \end{itemize}
\end{Mind}
综上所述，实际上只要比较最大值和第二大，第三大的值乘积和最大值和最小值，次小值的乘积选出最大的乘积即可。一次扫描数组时间代价O(n),空间代价存储第二大，第三大数的乘积和最小数和次小数的乘积即可。空间代价O(1)。
代码如下：
\cppfile[firstline=1,lastline=35]{code/arith/ex90/main.cpp}
\subsection{蚂蚁过河问题}
\begin{example}
    在一根长为L的水平木棍上有一群数量为n的蚂蚁，它们以每秒1cm/s的速度走到木棍一端就会掉下去。现在知道它们的起始位置是距离木根左端点的x处。但是不知道它们爬行的方向。在相向而行的两只蚂蚁相遇后，它们会掉头往反方向走。问所有蚂蚁都落下木棍的最快时间和最慢时间。
\end{example}
最短时间：所有蚂蚁朝同一个方向运动。最长时间，蚂蚁碰撞后掉头可以认为蚂蚁还是朝着各自的方向走。例如L为5,蚂蚁a和b在两端分别朝中间走，那么他们会相撞。之后各自返回，这里如果认为蚂蚁还是朝着原来的方向走（没有返回，实际上可以理解为碰撞后蚂蚁互换了身份，从时间的角度考虑不会有影响）。这时花费的最大时间就是蚂蚁走的最大时间。
\cppfile{code/ByteDance/src/antTime.cpp}
\subsection{找到数组中出现次数大于数组长度一半的数}
\begin{example}[找到数组中数字出现次数大于数组长度一半的数]
    对于数组中出现次数大于数组长度一半的数必定有它出现的次数大于其它所有数字出现的次数，对数组遍历如果数组元素和当前元素相等，次数times+1,不相等times-1,times不能为负数，如果times为0后下一个数字和当前保存的数字不相等则当前数字为此时的值，同时times为1。最后一个出现次数大于的数有可能是目标，有可能不是，所以还需要对该元素判断是否出现次数大于出现次数的一半(该算法时间复杂度为O(n))
\end{example}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=\textwidth]{graterhalf}
    \caption{出现次数大于数组长度一半}
\end{figure}
\cppfile{code/algorithm/src/getValue.cpp}
\subsection{数组中三个数的和为0}
\begin{example}[数组中三个数的和未0]

    给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
    注意：答案中不可以包含重复的三元组。



    示例：

    给定数组 nums = [-1, 0, 1, 2, -1, -4]，

    满足要求的三元组集合为：
    [
    [-1, 0, 1],
    [-1, -1, 2]
    ]
\end{example}
\begin{Mind}{三数和}{}
    对数组排序，然后遍历排序后的数组，获取元素，如果当前元素大于0则直接返回结果。（最小的数都大于0，无论如何都不可能通过加上两个更大的数变成0）。否则用左右指针分别指向当前元素的下一个元素和最后一个元素。对三个数求和：
    \begin{itemize}
        \item 三个数之和等于0，表示已经找到和为0的三个数。左指针右移，右指针左移。（左指针右移会使和大于0，右指针左移可能会使和小于0）直到两个指针指向同一个元素停止。开始当前元素右移一位进行下一轮判断。
        \item 如果三个元素和大于0，只能右指针左移以减小和达到为0的结果。
        \item 如果三个数和小于0，只能增加左指针达到为0的结果。
    \end{itemize}
    这里需要注意的是左右指针会遇到同样的元素，比如我们已经知道（-4）+（-1）+（2）不为0，左指针右移的结果还是（-4）+（-1）+（2）这时候求和已经没有必要，所以左指针直接右移，对于右指针也是这样。当前元素如果发现了和为0的组合，如果下一个元素和当前元素相同也没有求和的必要，因为之前已经求过了。
\end{Mind}
排序数组最快$O(n(logn))$，遍历数组$O(n)$,遍历当前元素后左右移动指针$(O(n^2))$,时间复杂度为：$O(n^2)$，空间复杂度为$O(1)$。
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{threeSum}
    \caption{求和示意图}
    \label{fig:threeSum}
\end{figure}
\begin{enumerate}
    \item 初始状态下，当前元素为-4，左右指针指向-1，2。（因为初始元素小于0，所以需要左右指针），和-3，所以需要左指针右移以加大和达到0。
    \item 左指针右移之后元素和上一次计算相同，左指针直接右移，直到左右指针指向末尾元素2遍历结束，说明当前元素为-4的时候没法找到和为0的元素，进行下一步比较。
    \item 当前元素为-1，（-1）+（-1）+2==0，找到结果，加入结果列表。左指针指右移，右指针左移。找到（-1）+（0）+（1）==0，找到结果加入结果列表，直到左右指针同时指向0元素为-1的时候遍历完成。
    \item 当前元素为-1，和上一步的元素相同，不用比较直接到下一个元素0。
    \item 当前和为大于0，只能左移右指针，左右指针同时指向1结束。
    \item 当前元素为1，已经大于0所以直接结束。
\end{enumerate}
\cppfile{code/algorithm/src/threeSum.cpp}
\subsection{寻找无序数组中的第k大元素}
先对前k个元素构建堆，遍历数组和堆顶元素比较，如果小于等于堆顶元素，则继续遍历，如果大于等于堆顶，则取代堆顶元素并调整堆。例如：
\begin{example}[最小的5个数]
    查找过程如\figref{fig:min_ks}
    \begin{figure}[!htbp]
        \centering
        \includegraphics[width=\textwidth]{min_ks}
        \caption{第k大的数过程}
        \label{fig:min_ks}
    \end{figure}
    将数组[7,5,15,3,17,2,20,24,1,9,12,8]中的前5个元素构建堆，最终的堆顶元素就是要找的第k大的数。
\end{example}
建堆的时间复杂度$O(k)$,遍历剩余数组的时间复杂度为$O(n-k)$，每次调整堆的时间复杂度为$O(log(k))$最坏情况下时间复杂度$O((n-k)logk+k)$当当k远小于n的情况下可以近似认为$O(nlog(k))$。空间复杂度为$O(1)$（原地交换需要一个临时变量）。
\cppfile[firstline=1,lastline=41]{code/arith/ex89/main.cpp}

\section{栈}
\subsection{单调栈}
\begin{example}{每日温度}
    请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
    例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
    提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
\end{example}
单调栈中从栈底到栈顶的元素对应的值依次减小，如果当前出现元素大于栈顶元素，直接入栈当前元素所在索引则破坏了这种规则，所以将栈中元素依次出栈，直到当前元素对应的索引小于栈顶元素时将此元素索引加入。
\begin{figure}[!htbp]
    \centering
    \includegraphics*[width=0.5\textwidth]{single_stack}
    \caption{单调栈}
    \label{fig:single_stack}
\end{figure}
入栈顺序：
\begin{itemize}
    \item 初始状态下栈为空，将0（73的索引）直接入栈。
    \item 当前元素为74（大于栈顶元素所指的值73）。将索引差值1（1-0=1）加入索引0指向的位置（result[0]=1），弹栈，当前元素所在索引1入栈。
    \item 当前元素为75（大于栈顶元素所指值74）。将索引差值1（2-1=1）加入索引1指向位置（result[1]=1），弹栈，当前元素2入栈。
    \item 当前元素71（小于栈顶元素指向值75），索引入栈。
    \item 当前元素69（小于栈顶元素71），索引入栈。
    \item 当前元素72（大于栈顶元素69），将索引差值（5-4=1）指向result[4]=1，弹栈，因为当前元素同时也大于当前栈顶元素，将差值（5-3=2）指向result[3]=2继续弹栈。之后此索引5入栈。
    \item 当前元素76（大于栈顶元素72），将索引差值（6-5=1）指向result[5]=1，弹栈，因为当前元素同时大于当前栈顶元素（75），将差值（6-2=4）指向result[2]=4继续弹栈，之后索引6入栈。
    \item 当前元素73（小于栈顶元素76），当前元素入栈。
\end{itemize}
\cppfile{code/DataStructAnd_Alg/src/dailyTemperatures.cpp}
\subsection{判断栈的出栈序列}
\begin{example}[判断出栈序列]
    输入两个整数序列，第一个序列表示栈的压栈顺序，第二个序列是栈的出栈顺序。假设栈中元素不相等，例如：入栈顺序为1,2,3,4,5，出栈顺序可能为5,4,3,2,1。但是4,3,5,1,2不是出栈序列。
    代码将入栈序列存放在队列中，比较的序列存放在栈中。从栈中获取元素，如果临时栈是空栈，就将队列中的元素入栈，直到遇到和出栈中元素相同的元素时，临时栈pop该元素。然后接着下次循环的时候
    栈不为空了，这时如果top元素和出栈top元素不同就从队列中将元素入栈，如果队列为空，并且临时栈中元素和出栈top元素不同则出栈顺序不对，返回false。否则如果出栈元素全部出栈说明，出栈匹配。
\end{example}
\cppfile[firstline=1,lastline=42]{code/arith/ex26/main.cpp}

\section{线段树}
线段树也是二叉树用来保存区间[1，……，N]和值，这个值根据不同的任务可以为区间的最大值，区间的和，区间元素替换。分解的区间和数n小于4N。
\begin{enumerate}
    \item[子区间划分]：对于给定区间[L,R]，只要L < R(直到L=R到达叶子节点) ，线段树就会把它继续分裂成两个区间。
    首先计算 M = (L+R)/2，左子区间为[L,M]，右子区间为[M+1,R]，然后如果子区间不满足条件就递归分解。
    以区间[1..13]的分解为例，分解结果见下图：
    \begin{figure}[H]
        \centering
        \includegraphics[width=\textwidth]{seg_tree1}
        \caption{线段树示例}
    \end{figure}
    自下而上合并规则：如果两个孩子有相同的父节点，用父节点代替两个孩子节点,可以看区间[2,12]=[2]+[3,4]+[5,7]+[8,10]+[11,12]
    \begin{figure}[H]
        \centering
        \includegraphics[width=\textwidth]{seg_tree2.pdf}
        \caption{自底向上}
    \end{figure}
    \begin{figure}[H]
        \centering
        \includegraphics[width=0.5\textwidth]{seg_tree3.pdf}
        \includegraphics[width=0.5\textwidth]{seg_tree4.pdf}
        \caption{自顶向下}
    \end{figure}
    \item 如何进行区间统计？假设13个数分别是1,2,3,4,1,2,3,4,1,2,3,4,1在区间之后标上的数字为区间内元素的和。
          \begin{figure}[H]
              \centering
              \includegraphics[width=0.5\textwidth]{seg_tree5.pdf}
              \caption{计算和}
          \end{figure}
          [1,12]=[2]+[3,4]+[5,7]+[6,10]+[11,12]计算5个数就可以计算出[2,12]的值。
    \item 修改点的值,将数组元素A的第6个数A[6]加上7。
          \begin{figure}[H]
              \centering
              \includegraphics[width=0.5\textwidth]{seg_tree6.pdf}
              \caption{计算区间和}
          \end{figure}
\end{enumerate}

\section{字符串}
\subsection{字符串的快速匹配算法KMP}
部分匹配表(PMT)：\textbf{前缀表达式}\footnote{字符串除了最后一个字符外所有可能的顺序字符组合}和\textbf{后缀表达式}\footnote{字符串除了第一个字符外前面所有字符的顺序组合}的交集的最大长度。
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{kmp_match1}
    \caption{kmp匹配过程(1)}
    \label{fig:kmp_match1}
\end{figure}
匹配字符串的PMT计算如\tabref{tab:PMT_computer}，
\begin{table}[!htbp]
    \centering
    \caption{计算部分匹配表}
    \begin{tabular}{p{0.2\textwidth}p{0.3\textwidth}p{0.3\textwidth}p{0.2\textwidth}}
        \toprule
        字符串   & 前缀字符串                                                & 后缀字符串                                                & 交集长度 \\
        \midrule
        A        & 无                                                        & 无                                                        & 0        \\
        AB       & B                                                         & A                                                         & 0        \\
        ABA      & \textcolor{red}{A}, AB                                    & \textcolor{red}{A}, BA                                    & 1        \\
        ABAB     & A, \textcolor{red}{AB}, ABA                               & B, \textcolor{red}{AB}, BAB                               & 2        \\
        ABABA    & \textcolor{red}{A}, AB, \textcolor{red}{ABA}, ABAB        & \textcolor{red}{A}, BA, \textcolor{red}{ABA}, BABA        & 3        \\
        ABABAB   & A, AB, ABA, \textcolor{red}{ABAB}, ABABA                  & B, AB, BAB, \textcolor{red}{ABAB}, BABAB                  & 4        \\
        ABABABC  & A, AB, ABA, ABAB, ABABA, ABABAB                           & C, BC, ABC, BABC, ABABC, BABABC                           & 0        \\
        ABABABCA & \textcolor{red}{A}, AB, ABA, ABAB, ABABA, ABABAB, ABABABC & \textcolor{red}{A}, CA, BCA, ABCA, BABCA, ABABCA, BABABCA & 1        \\
        \bottomrule
    \end{tabular}
    \label{tab:PMT_computer}
\end{table}
即可得到PMT[0,0,1,2,3,4,0,1]。根据\figref{fig:kmp_match1}匹配到索引为6的元素时$Target(A) \neq Pattern(C)$这时Target之前的PMT[j-1](5)个元素与Pattern的0到PMT[j-1]位相同，即(ABABAB=ABABAB)。这是因为字符串Target在 i 位失配，也就意味着Target从 i−j 到 i 这一段是与模式字符串的 0 到 j 这一段是完全相同的。而我们上面也解释了，字符串Pattern从 0 到 j−1 ，在这个例子中就是”ABABAB”，其前缀集合与后缀集合的交集的最长元素为"ABAB"， 长度为4。所以就可以断言，Target字符串中i指针之前的 4 位一定与模式字符串的第0位至第 4 位是相同的，即长度为 4 的后缀与前缀相同。这样一来，我们就可以将这些字符段的比较省略掉。具体的做法是，保持i指针不动，然后将j指针指向模式字符串的PMT[j −1]位即可。

简言之，以\figref{fig:kmp_match2}中的例子来说，在 i（6） 处失配，那么Target字符串和Pattern字符串的前边6位就是相同的。又因为Pattern字符串的前6位，它的前4位前缀和后4位后缀是相同的，所以我们推知Target字符串i之前的4位和Pattern字符串开头的4位是相同的。

我们就可以使用PMT加速字符串的查找了。我们看到如果是在 j 位失配，那么影响 j 指针回溯的位置的其实是第 j −1 位的 PMT 值，所以为了编程的方便， 我们不直接使用PMT数组，而是将PMT数组向后偏移一位。我们把新得到的这个数组称为next数组。下面给出根据next数组进行字符串匹配加速的字符串匹配程序。其中要注意的一个技巧是，在把PMT进行向右偏移时，第0位的值，我们将其设成了-1，这只是为了编程的方便，并没有其他的意义。在本节的例子中，next数组如\tabref{tab:next_array}所示
\begin{table}[!htbp]
    \centering
    \caption{next数组}
    \begin{tabular}{p{0.1\textwidth}p{0.1\textwidth}p{0.1\textwidth}p{0.1\textwidth}p{0.1\textwidth}p{0.1\textwidth}p{0.1\textwidth}p{0.1\textwidth}p{0.1\textwidth}}
        \toprule
        索引 & 0  & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\
        \midrule
        字符 & A  & B & A & B & A & B & C & A \\
        PMT  & 0  & 0 & 1 & 2 & 3 & 4 & 0 & 1 \\
        next & -1 & 0 & 0 & 1 & 2 & 3 & 4 & 0 \\
        \bottomrule
    \end{tabular}
    \label{tab:next_array}
\end{table}

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{kmp_match2}
    \caption{kmp匹配跨越移动}
    \label{fig:kmp_match2}
\end{figure}
现在，我们再看一下如何编程快速求得next数组。其实，求next数组的过程完全可以看成字符串匹配的过程，即以Pattern字符串为Target字符串，以Pattern字符串的前缀为Target字符串，一旦字符串匹配成功，那么当前的next值就是匹配成功的字符串的长度。具体来说，就是从模式字符串的第一位(注意，不包括第0位)开始对自身进行匹配运算。 在任一位置，能匹配的最长长度就是当前位置的next值。如\figref{fig:BMT}，这里以next(6)的计算为例，因为next[0]=-1,计算next[1]为A的前后缀的交集的最大长度0，next[2]为AB前后缀交集最大长度0，next[6]为的前缀为A、AB、ABA、ABAB、ABABA后缀为B、AB、BAB、ABAB、BABAB。交为ABAB长度为4。

\begin{figure}[!htbp]
    \centering
    \includegraphics[width=\textwidth]{BMT}
    \caption{对应的位置关系}
    \label{fig:BMT}
\end{figure}
\[P[0:k-1] = P[j-k:j-1],k=1,j=3\]
因为当$T[i]\neq P[j],C\neq D$时$T[i-j:i-1] == P[0:i-1]$，由$P[0:k-1] = P[j-k:i-1](ABA=ABA)$必然有：$T[i-k:i-1] = P[0:k-1],A=A$。

通常将每个位置j对应的值k放入next[ ]数组。k实际上为第一个不匹配的字符所在位置的左边字串的两边相等的元素。,如何求这里的k？
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{kmp4}
    \caption{第一个字符就不匹配}
    \label{fig:kmp_4}
\end{figure}

\figref{fig:kmp_4}这时候第一个字符串不匹配，匹配字符串为0,匹配字符串左边和右边相等的元素个数不存在，这里初始化为-1,即next[0] = -1。
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{kmp5.pdf}
    \caption{字符串第二个字符不匹配}
    \label{fig:kmp_5}
\end{figure}
next vector实现用于调试查看代码执行流程。
\cppfile{code/string/kmp/next.cpp}
\cppfile[firstline=1,lastline=41]{code/string/kmp/main.cpp}
\subsection{字符串的全排列}
对于abc字符串中的每一位，依次交换其和剩余字符串的位置。例如abc第一位和a、第二位b、第三位c交换分别为abc、bac、cba。对于交换之后的部分假定已经全部排列好了。例如bc全排列好了应该是bc和cb。那第一次分割a和bc的这一组结果就是abc和acb。同理其它的也可以按照这个来，分别即可得到bac和bca以及cba和cab。对于bc应该怎么排列？同样按照第一位和剩余位交换分为b和c以及c和b。对于剩下的c按照同样的方式分割。但是因为c已经没有后续字母了，它的排列为c。由此可知算法为：将字符串的每一位分别和后面的每一位交换。这样交换的后半部分长度将少1（少了第一位），对于这个字串做同样的操作指导字串长度为1（不可分割）则结束分割。因此递归结束的条件是当前需要分割的字符串k（位置k）已经达到字符串末尾（length(str)-1）。还有一个问题是交换后需要交换回来，比如abc中a和第二位交换变成了bac。假设ac排好了（good(ac)）轮到cba这组操作的字符串递归操作的时候字符串已经由原来的abc变成了bac。无疑这样将导致后续交换出问题。所以当b(good(ac))后需要将其换回abc。
\cppfile{code/arith/Permutation.cpp}
\subsection{替换字符串中的指定字符}
比如We are happy中的空格替换成We\%20are\%20happy。
\begin{Mind}{}{}
    遍历字符串获取字符串空格数量，设置两个指针P1一个指向字符串的结尾，一个指针P2指向拟插入字符后的空间的末尾（这里有两个空格，则插入到P1后面+4的位置）将P1指向的内容一个个往后移动P2指向的最后，如果遇到空格P2指针移动到移动字符串(Happy)的前面,在此插入\%20,同时移动指针P2的位置。重复操作直到两个指针指向的位置相等即可停止。
\end{Mind}
\begin{algorithm}
    \caption{替换字符串算法}
    \begin{algorithmic}
        \REQUIRE 字符串长度能够容纳添加空格后的字符串。P1指向字符串尾部，P2指向插入字符串后的尾部。
        \WHILE{P1指针指向位置和P2指向位置不同}
        \STATE 往字符串最后面移动非空格字符串，指针P2指向移动字符串后的前一个位置，同时插入待插入的字符串。
        \ENDWHILE
    \end{algorithmic}
\end{algorithm}
整个算法过程：
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{replace_string}
    \caption{替换空格算法过程}
\end{figure}
\cppfile{code/algorithm/src/replaceSpace.cpp}
\subsection{正则表达式匹配}
\begin{example}[实现'.'和'*'的正则表达式匹配]
    当匹配字符串的下一个字符是"*"的时候，可能存在多种匹配方式。
    \begin{enumerate}
        \item 在模式字符串向后移动两个字符，相当于*前面的内容和*一起忽略。
        \item 如果模式字符串中的第一个字符和字符串中的第一个字符匹配，则在字符串上向后移动一个字符，但是对于模式可以：
              \begin{enumerate}
                  \item 在模式上向后移动两个字符。
                  \item 在模式上保持不变。
              \end{enumerate}
    \end{enumerate}
\end{example}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{re_code.pdf}
    \caption{正则表达式匹配过程}
\end{figure}
\cppfile[firstline=1,lastline=30]{code/offer/ex26/main.cpp}
\subsection{判断一个字符串是不是数值}
\begin{example}[判断一个字符串是不是数值]
    字符串是科学计数法表示的字符串如1.23e-3,或者1.23E-3
\end{example}
\cppfile[firstline=1,lastline=31]{code/offer/27/main.cpp}
\subsection{翻转字符串}
\begin{example}[翻转字符串]
    如输入"I am a student."输出结果"student. a am I"。思路：先翻转字符串(".tneduts a ma I")，然后对空格隔开的字符串再次翻转("student. a am I")
\end{example}
\cppfile[firstline=1,lastline=30]{code/arith/ex77/main.cpp}
\subsection{处理重复字符串}
要求输入字符串中XXYY类被处理为XXY，但是像AABBCC包含有两个XXYY，分别为AABB和BBCC这样只处理AABB。XXX被处理为XX。

\textbf{思路：}这里先判断是不是XXX类型，如果是就删除第一个X，这样XXX就被处理成了XX。然后判断是不是XXYY，如果是则删除第三个元素Y。从字符串开始判断直到判断结束。
\cppfile[firstline=1,lastline=22]{code/arith/ex95/main.cpp}
\subsection{寻找字符串中第一次出现的字符}
\begin{example}[寻找字符串中第一次出现的字符]
    将字符串中每一个值用字符:count表示，通过字符获取次数为1的字符。
\end{example}
\cppfile[firstline=1,lastline=20]{code/STL/ex2/main.cpp}
\subsection{打印最大的n位数}
算法流程为：
\begin{itemize}
    \item 给定n，生成一个n+1的cstring，最后一位'$\backslash 0$'。
    \item Increment给字符串加上1（这里有判断0位有没有进位，如果有说明已经到达n位最大值。）打印的时候是输出一个打印一个，这样就不用将所有数据存在列表中了。
    \item PrintNumber打印字符串，因为不能打印字符串前面的0,所以必须从前往后判断，元素值不为0,输出值。
\end{itemize}
\cppfile[firstline=1,lastline=54]{code/offer/ex21/main.cpp}
\subsection{超大数相加}
\begin{itemize}
    \item 每个数保存在栈中，取出栈顶元素，求和如果和大于10,就对10取余获得进位1和余数添加到结果栈和进位栈。
    \item 反复执行第一步知道一个栈为空。
    \item 将非空的栈元素添加到结果栈中。
\end{itemize}
\cppfile[firstline=1,lastline=40]{code/offer/ex22/main.cpp}
\section{链表部分}
\subsection{获取链表中倒数第k个元素}
\begin{example}[单链表获取倒数第k个元素]
    单链表无法反向获取元素，获取倒数第k各元素相当于获取正数第n-k(下标从0开始)。通过两个指针，一个指针在另一个指针后面k，然后同时往后移动，当后面的指针指向空的时候前一个指针就能指向倒数第k个。
\end{example}
\cppfile[firstline=1,lastline=40]{code/arith/ex16/main.cpp}
\subsection{反转链表}
\begin{example}[翻转链表]
    翻转链表，如果让后面的元素直接指向前面的元素会出现元素后面的元素无法访问，因为链表只能顺序访问。所以必须将后一个节点保存。
    \begin{figure}[H]
        \centering
        \includegraphics[width=0.5\textwidth]{reverse_link.pdf}
        \caption{反转链表}
    \end{figure}
    整个反转操作需要保存当前节点的前一个节点pPrenode，后一个节点pNext，通过当前节点向后移动。直到pNext为nullptr则表明pNext到达链表末尾。此时反转后链表头为当前节点。操作如\figref{fig:reverselink}：
    \begin{figure}
        \centering
        \includegraphics[width=\textwidth]{reverselink.pdf}
        \caption{反转链表操作}
        \label{fig:reverselink}
    \end{figure}
\end{example}
\cppfile[firstline=13,lastline=32]{code/arith/ex18/main.cpp}
时间复杂度：$O(n)$ 。 假设 $n$ 是列表的长度，时间复杂度是 $O(n)$。空间复杂度：$O(1)$ 。
\subsection*{链表反转（递归）}
通过不断传入head->next指向的节点，指向最后一个元素tail。获取最后一个元素，此时head栈中保留的是最后一个元素的前一个元素。head->next->next就能实现最后一个元素（4）和前一个元素（3）的反转，但是此时是双向指针，需要将前一个指针指向nullptr。此时反转完成，退栈，此时栈中保留的元素是当前元素的前一个元素（2先入后出）。反复递归调用即可实现反转。函数调用栈帧变化如\figref{fig:linkstack}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.5\textwidth]{linkstack}
    \caption{递归函数栈帧变化}
    \label{fig:linkstack}
\end{figure}
递归反转的逻辑图如\figref{fig:reverselin_rec}第四（k）个节点已经反转，这时候需要将第三（k-1）个节点指向其前一个节点（$P_{k-1}->next(P_{k-2})->next = P_{k-1}$）
\begin{figure}
    \centering
    \includegraphics[width=0.6\textwidth]{reverselink_rec}
    \caption{递归反转链表流程}
    \label{fig:reverselin_rec}
\end{figure}
递归实现反转链表：
\begin{cpp}
    Node* reverseLinkListRec(Node* head){
            if(head == nullptr||head->next == nullptr)
            return head;
            Node* tail = reverseLinkListRec(head->next);
            head->next->next = head;
            head->next = nullptr;
            return tail;

        };
\end{cpp}
时间复杂度：$O(n)$ 。 假设 n 是列表的长度，那么时间复杂度为 $O(n)$。空间复杂度：$O(n)$ 。 由于使用递归，将会使用隐式栈空间。递归深度可能会达到 nn 层。
\subsection{融合链表}
融合两个有序元素链表并保持链表元素的顺序。通过定义融合后的节点pMergehead,当链表A的头节点的数据小于B的头节点数据的时候下一步融合的是A的下一个节点组成的链表和B链表。融合后的节点pMergehead指向的即两个融合之后的结果，反复递归调用，直到两个链表都到了链表尾部融合终止。需要注意的是，两个参数分别指向两个链表的融合节点，当某一个节点指向nullptr的时候表示这个链表已经达到了末尾，同时意味着另一个链表没有达到末尾，这时候返回没有达到末尾的节点。
\cppfile[firstline=12,lastline=30]{code/arith/ex19/main.cpp}
时间复杂度$O(m+n)$，空间复杂度$O(m+n)$。
\subsection*{递归实现链表融合}
创建指向链表头的指针节点，通过不断对比两个链表的元素，用prenode指向其中元素较小的节点，反复调用知道任何一个链表到达链表尾部。这时候另一个链表还没有到达尾部，需要判断一下prenode下一个节点指向的节点是否为l1且为空，是则指向l2否则指向l1。算法处理如\figref{fig:merge_link_rec}：
\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{merge_link_rec}
    \caption{递归融合链表}
    \label{fig:merge_link_rec}

\end{figure}
\begin{cpp}
    Node *mergeLink(Node *l1, Node *l2) {
            Node *prenode = new Node(-1);
            Node *head = prenode;
            while (l1 != nullptr && l2 != nullptr) {
                    if (l1->value <= l2->value) {
                            prenode->next = l1;
                            l1 = l1->next;
                        } else {
                            prenode->next = l2;
                            l2 = l2->next;
                        }
                    prenode = prenode->next;
                }
            prenode->next = l1 == nullptr ? l2 : l1;
            return head->next;
        }
\end{cpp}
时间复杂度$O(m)+O(n)$，空间复杂度$O(1)$
\subsection{链表中的公共节点}
\begin{example}[链表中的第一个公共节点]
    遍历两个链表获取链表长度m,n，对长的链表m先前进(m-n),然后两个链表的指针同时往后移发现相同的节点即返回。
\end{example}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{same_node}
    \caption{公共节点}
\end{figure}
\cppfile[firstline=14,lastline=54]{code/arith/ex51/main.cpp}

\section{区间问题}
\subsection{是否可以参加所有会议}
给定一系列的会议时间间隔，包括起始和结束时间$[[s_1,e_1],[s_2,e_2],\ldots (s_i < e_i)$，确定一个人是否可以参加所有会议。
\begin{example}
    给定区间=[[0,30]，[5,10]，[15,20]]，返回false。
\end{example}
\begin{Mind}{会议问题思路}{}
    将起始、终止对按照起始从小到大排序。排序对后的第一对第一个元素为起始时间，第二个为终止时间。那最小的起始时间开始，对第一对，终止时间肯定大于起始时间。这时候起始时间变成第一对的终止时间end，开始看第二对，如果第二队起始时间小于刚刚的终止时间，表明第二对时间和第一对重复了，那就是产生冲突无法参加两个会议。否则将第二对的终止时间给终止时间end。
\end{Mind}
\cppfile[firstline=1,lastline=13]{code/arith/ex91/main.cpp}
\subsection{所需会议室}
给定一系列的会议时间间隔intervals，包括起始和结束时间$[[s_1,e_1],[s_2,e_2],...] (s_i < e_i)$，找到所需的最小的会议室数量。给出 intervals = [(0,30),(5,10),(15,20)], 返回 2。

扫描线算法：
\begin{itemize}
    \item 将所有区间从小到大排列。
    \item 将排列的区间起点设置为1，终点设置为-1。
    \item 扫描整个区间，求出和最大的数为结果。
\end{itemize}
扫描线算法示意图如\figref{fig:scan_line}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=\textwidth]{scan_line.pdf}
    \caption{扫描线算法示意图}
    \label{fig:scan_line}
\end{figure}
代码如下：
\cppfile[firstline=1,lastline=22]{code/arith/ex92/main.cpp}
\subsection{区间融合问题}
\begin{example}[区间融合]
    给出一个区间的集合，请合并所有重叠的区间。示例 1:

    输入: [[1,3],[2,6],[8,10],[15,18]]
    输出: [[1,6],[8,10],[15,18]]
    解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

    示例 2:
    输入: [[1,4],[4,5]]
    输出: [[1,5]]
    解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
\end{example}
\cppfile{code/arith/ex93/src/merge_span.cpp}
\section{双指针问题}
\subsection{装水最多的容器}
给你 n 个非负整数 $a_1,a_2,\ldots,a_n$，每个数代表坐标中的一个点 $(i, a_i)$ 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 $(i, a_i)$ 和 $(i, 0)$ 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
\begin{figure}[H]
    \centering
    \includegraphics[width=0.4\textwidth]{maxArea}
    \caption{盛水最多的容器示意图}
    \label{fig:maxArea}
\end{figure}
$Water=min(height[left],height[right])*(right-left)$盛水多少主要个容器高度和容器间隔的宽度$(left-right)$有关，装水量由左右两边容器中更短$min(height[left],height[right])$的容器决定。在 $(right-left)$ 最大的时候想装最多的水，只能依靠移动left或者right抵消$(right-left)$的减小，即移动左右的同时保证增加$min(height[left],height[right])$。最开始情形左右 left 和 right装水$(8-0)*1=8$,现在希望获得更多的水则只能移动短的left容器使得找到height[1] = 8。这时候容器中的水$(8-1)*7=49$ 宽度减少了1,但是因为最短容器变大导致装水更多。这时候我们需要和钢材一样的方法移动短边以希望增大盛水量（left和right的高度需要判断一下谁更小，决定移动，left只能往右边移动，right只能往左边移动）。
\cppfile{code/algorithm/src/maxArea.cpp}
\section{动态规划}
在开始讲解动态规划时我们先看一个这样的问题，现在有一根长度为 n 的钢材，不同长度的钢材价格不一样，价格列表如下\tabref{tab:steel_price}：
\begin{table}[H]
    \centering
    \caption{钢材长度与价格}
    \begin{tabular}{ccccccccccc}
        \toprule
        长度   & 1 & 2 & 3 & 4 & 5  & 6  & 7  & 8  & 9  & 10 \\
        \midrule
        价格 p & 1 & 5 & 8 & 9 & 10 & 17 & 17 & 20 & 24 & 30 \\
        \bottomrule
    \end{tabular}
    \label{tab:steel_price}
\end{table}
现在给你一个长度为 n 的钢材，请问如何切割能保证钢材卖出的价格最高？

我们可以分析一下，给定比较小的长度为 n 的钢材切割后的最大售价。
\begin{table}[H]
    \centering
    \caption{钢材长度与价格}
    \begin{tabular}{ccccccccccc}
        \toprule
        长度                  & 1 & 2 & 3 & 4  & 5  & 6  & 7  & 8  & 9  & 10 \\
        \midrule
        最大切分价格 maxPrice & 1 & 5 & 8 & 10 & 13 & 17 & 18 & 22 & 25 & 30 \\
        \bottomrule
    \end{tabular}
    \label{tab:steel_total_price}
\end{table}
如\tabref{tab:steel_total_price} ，长度为5的钢材，我们可以选择将其切分为1+4、2+3或者不切分，分别对应的价格为10、13、10。所以可以得到长度为5的最大价格为13。另maxPrice(n)表示长度为n的钢材切分能获得的最大价格。则$maxPrice(n) = max(p[1]+p[n-1],p[2]+p[n-2],\ldots p[n-1,1])$，这里实际上不需要计算 n-1 次，因为$p[1]+p[n-1] = p[n-1]+p[1]$，代码实现：
\cppfile[firstline=2,lastline=18]{code/algorithm/dp/src/maxSteelPrice.cpp}
至此你可能认为问题已经得到了求解，但是事实上上述解法是错误的。原因在于你的钢材也许不会被切分为两段而是三段。只是刚好这么几个数值上两段和多段的结果相同而已。

考虑多段，我们再来回头看最大价格的计算，则$maxPrice(n) = max(p[i]+maxProce(n-i)),i=1\ldots,n-1$，这时我们认为钢材的最大价格为钢材切割后，两段的价格。不过要求其中一段为长度r的最大价格。例如$maxPrice(5) = max(p[2]+maxPrice(3))=8+5=13$，最朴素实现：
\cppfile[firstline=19,lastline=30]{code/algorithm/dp/src/maxSteelPrice.cpp}
朴素实现使用递归计算，递归计算的问题在于重复计算。例如：计算maxPrice(4)，需要计算maxPrice(3)+p[1]、maxPrice(2)+p[2]、maxPrice(1)+p[3]、maxPrice(0)+p[4]，而计算 maxPrice(3) 同样需要计算 maxPrice(2)+p[1]、maxPrice(1)+p[2]、maxPrice(0)+p[3]。这样整个计算图如\figref{fig:maxSteelPrice}
\begin{figure}[H]
    \centering
    \includegraphics[width=0.7\textwidth]{maxSteelPrice}
    \caption{maxPrice(4)的递归计算}
    \label{fig:maxSteelPrice}
\end{figure}
优化算法：
\begin{itemize}
    \item 自顶向下递归计算，通常也称为带备忘录的自顶向下。
    \item 自底向上
\end{itemize}
解法1,如果我们计算maxPrice(2)的时候因为其值没有，所以需要递归计算实现maxPrice(2)。如果maxPrice(2)计算了，那么计算 maxPrice(4) 和 maxPrice(3)的时候都能使用，自定向下计算的优化在于保存了每个值的结果。这样就不用递归计算了：
\cppfile[firstline=31,lastline=48]{code/algorithm/dp/src/maxSteelPrice.cpp}
解法2：自底向上，此算法是上面算法的逆过程，我们很容易其得到 maxPrice(0)=0 求解 maxPrice(1) 的时候就可以直接用到maxPrice(0)，如果要求 maxPrice(n) 我们则需要依次计算 maxPrice(0)-maxPrice(n-1)
\cppfile[firstline=49,lastline=67]{code/algorithm/dp/src/maxSteelPrice.cpp}

将一个大问题分解为递归的子问题，子问题有最优解，整个问题就有最优解。求解动态规划问题一般流程如下：
\begin{itemize}
    \item 状态：问题解的描述，例如：DP[i][j] 表示 i 到 j 元素和的最大值。
    \item 转移方程：最优问题拆分为子问题之后的表达式。
    \item 边界条件：最基本情况下问题的解。
\end{itemize}
\subsection{最长公共子序列}
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
\begin{itemize}
    \item 状态：DP[i][j]表示输入字符串a从起点0到i（不包含i），和字符串b从起点0到j（不包含j）的最长公共字串长度。
    \item 转移方程：
          \begin{equation}
              DP[i][j] =
              \begin{cases}
                  0\quad i=0\quad or\qquad j=0                  \\
                  DP[i-1][j-1]+1\quad a[i]=b[j]                 \\
                  max(DP[i-1][j],DP[i][j-1])\quad a[i]\neq b[j] \\
              \end{cases}
          \end{equation}
    \item 边界条件：字符串a和b的长度为0的时候结果为0。
\end{itemize}
\cppfile{code/algorithm/src/longestCommonSubsequence.cpp}
时间复杂度：$O(mn)$，其中 $m$ 和 $n$ 分别是字符串text1和text2的长度，二位数组有 m+1 行和 n+1列，所需要对 dp 中每个元素计算。空间复杂度： $O(mn)$ ，其中 m 和 n 分别是字符串 test1 和 test2 的长度，因为不包含当前数值，所以行和列分别都需要多开辟一个空间，数组长度为 $m+1$ 行和 $n+1$ 列数组。
\subsection{打家劫舍}
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
\begin{Textcode}
    输入：[1,2,3,1]
    输出：4
    解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
    偷窃到的最高金额 = 1 + 3 = 4 。
    示例 2：

    输入：[2,7,9,3,1]
    输出：12
    解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
    偷窃到的最高金额 = 2 + 9 + 1 = 12 。
\end{Textcode}
\begin{itemize}
    \item 状态：DP[i]表示从索引索引为0到i-1能偷窃到的最高金额。
    \item 转移方程：
          \begin{equation}
              DP[i] = max(DP[i-1],DP[i-2]+value[i-1])
          \end{equation}
    \item 边界条件：DP[0]=0,DP[1]=value[0]。
\end{itemize}
自底向上实现：
\cppfile[firstline=27,lastline=41]{code/algorithm/dp/rob.cpp}
\subsection{最长递增子序列}
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
\begin{Textcode}
    示例 1：
    输入：nums = [10,9,2,5,3,7,101,18]
    输出：4
    解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
    示例 2：
    输入：nums = [0,1,0,3,2,3]
    输出：4
    示例 3：
    输入：nums = [7,7,7,7,7,7,7]
    输出：1
\end{Textcode}
\begin{itemize}
    \item 状态：$DP[i]$表示从起点到$nums[i]$（包括）递增数组的最大长度。
    \item 转移条件：假设$DP[j]$计算出来了，需要获取$DP[i],j<i$这时候,如果$nums[i]>nums[j]$则结果为$DP[i] = DP[j]+1$
    \item 边界条件：$DP[0]=1$
\end{itemize}
\cppfile{code/algorithm/src/lengthOfLIS.cpp}
如\figref{fig:longest_nums}，计算$DP[5]$我们需要拿着$nums[5]=7$分别和$nums[0]=10,nums[1]=9,nums[2]=2,nums[3]=5,nums[4]=3$比较、如果当前值$DP[5]$大于其之前的元素，则当前值为$DP[4]+1$。
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=\textwidth]{longest_nums}
    \caption{最长递增子序列}
    \label{fig:longest_nums}
\end{figure}
\subsection{找零钱问题}
找硬币问题：现在有数额指定的硬币(例如：1、3、5)，给定一个金额n，希望能找到最少的硬币其和等于n。
\begin{itemize}
    \item 状态：原来问题中通过切分问题能改变的量，这个量通常是我们需要达到的目标值。这里假设能找到的和为n的最少硬币数为f(n)。如果我们通过途径计算到了f(n-k)，那$f(n)=min(f(n-k)+1|k\in coins)$。
    \item 转移条件：对于每一个状态，可以作出一个选择以改变当前的状态。比如这里min的操作就是选择，选择到底是通过n-k获取的最小硬币数f(n-k)+1(这个硬币)还是f(n-k)（没有k只额个硬币则+0）)，怎么选是由哪种选法决定的。
    \item 边界条件：超过最小子问题的问题。这里比如n=0的时候无法这个值为0,n<0的时候找不到这个值。结果为-1
\end{itemize}

DP用来存储计算结果，DP[n]表示使用零钱凑出金额n需要的最小硬币数。例如硬币是[1,2,5]凑出11需要的最小金额数为DP[11]。DP[0]=0,DP[1]=1(一个面值为1的硬币),DP[2]=1(一个面值为2的硬币)，DP[3]=2(面值为1和2的硬币两个)。
计算面值为2的最小硬币数是：
\begin{itemize}
    \item DP[0] = 0
    \item DP[1] = 1
    \item DP[2] = min(DP[2-1]+1,DP[2-2]+1,DP[2-5]+1) 中的最小值 = 1
    \item DP[3] = min(DP[3-1]+1,DP[3-2]+1,DP[3-5]+1)中最小值 = 2
\end{itemize}
自顶向下实现：
\cppfile[firstline=5,lastline=33]{third_party/coding/cxx/algorithm/dp/src/coinChange.cpp}
自底向上实现
\cppfile[firstline=40,lastline=58]{third_party/coding/cxx/algorithm/dp/src/coinChange.cpp}

\subsection{最长回文字串}
\begin{Textcode}
    给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

    示例 1:
    输入:
    "bbbab"
    输出:

    4
    一个可能的最长回文子序列为 "bbbb"。
    示例 2:
    输入:

    "cbbd"
    输出:

    2
\end{Textcode}
\begin{itemize}
    \item 状态：dp[i][j]表示从起点i到终点j的最长公共字串的长度。
    \item 转移条件：如果起点元素i和终点元素j相等的话，dp[i][j]=dp[i+1][j-1]+2，否则dp[i][j] = max(dp[i][j-1],dp[i+1][j])。转移条件为max(dp[i+1][j-1]+2,dp[i+1][j-1])。这里需要特别注意的是：因为dp[1][3]需要计算dp[2][3]和dp[1][2]，所以初始化数组的时候先计算start大的值。
    \item 边界条件：dp[i][j]这里i=j时结果为1。
\end{itemize}
\begin{table}[!htbp]
    \centering
    \begin{tabular}{|c|c|c|c|c|c|}
        \hline
        \diagbox{start}{end} & 0 & 1 & 2 & 3 & 4 \\
        \hline
        0                    & 1 & 2 & 3 & 3 & 4 \\
        1                    & 0 & 1 & 1 & 2 & 3 \\
        2                    & 0 & 0 & 1 & 2 & 3 \\
        3                    & 0 & 0 & 0 & 1 & 1 \\
        4                    & 0 & 0 & 0 & 0 & 1 \\
        \hline
    \end{tabular}
    \caption{DP计算表}
\end{table}
\cppfile{code/algorithm/src/longestPalindromeSubseq.cpp}

\subsection{机器人的路径}
一个机器人在$m\times n$大小的地图的左上角（起点）。机器人每次向下或向右移动。机器人要到达地图的右下角（终点）。可以有多少种不同的路径从起点走到终点？备注：m和n小于等于100,并保证计算结果在int范围内
如果m和n有一个元素为1,那么结果将只能横向或者纵向走到终点，此时走法只有一种。这里假设dp[m][n]表示从起点走到（m、n）所有可能的步数：
\begin{itemize}
    \item 状态：dp[i][j]表示从起点i到终点j的所有可能步数。
    \item 转移条件：dp[i][j]可以通过走到位置[i-1][j]向下走和位置[i][j-1]向右走获得。转移条件为dp[i][j] = dp[i][j-1]+dp[i-1][j]。
    \item 边界条件：如果目的位置在第一行或者第一列，那么走到目标位置只能通过向右或者向下达到，可能步数为1。
\end{itemize}
自顶向下实现：
\cppfile[firstline=8,lastline=28]{code/algorithm/dp/uniquePaths.cpp}
自底向上实现：
\cppfile[firstline=30,lastline=48]{code/algorithm/dp/uniquePaths.cpp}
\begin{table}[!htbp]
    \centering
    \begin{tabular}{|c|c|c|c|c|}
        \hline
        起点 & 1 & 1 & 1  & 1        \\
        \hline
        1    & 1 & 1 & 1  & 1        \\
        \hline
        1    & 2 & 3 & 4  & 5        \\
        \hline
        1    & 2 & 5 & 9  & 14       \\
        \hline
        1    & 3 & 8 & 17 & 31(终点) \\
        \hline
    \end{tabular}
\end{table}
\cppfile{code/algorithm/dp/src/uniquePaths.cpp}
\subsection{礼物的最大价值}
\begin{example}[礼物的最大价值]
    \begin{equation*}
        \begin{bmatrix}
            1  & 10 & 3  & 8  \\
            12 & 2  & 9  & 6  \\
            5  & 7  & 4  & 11 \\
            3  & 7  & 16 & 5
        \end{bmatrix}
    \end{equation*}
    \begin{itemize}
        \item 状态：$dp[i][j]$表示到达$[i,j]$礼物的最大价值（grid表示上面的价值矩阵）。
        \item 转移条件：$dp[i][j]$可以通过走到位置$[i-1][j]$获得的最大价值$dp[i-1][j]$和走到位置$[i][j-1]$获得的最大价值$dp[i][j-1]$加上$grid[i][j]$获得。当然这两条路径不能都走，所以决定走那条路决定于哪个累计和更大。例如如果$dp[i][j-1]$更大，那么走$dp[i-1][j]$是没有意义的。
        \item 边界条件：如果最大价值来源于第一行，那么获得最大价值只能从位置$[i][j]$的左边达到，如果是第一列同理只能通过位置$[i][j]$的上面达到。如果只有一行一列，那么最大价值就是当前值$grid[i][j]$。
    \end{itemize}
    \begin{equation}
        \begin{split}
            dp(i,j)=\begin{cases}
                 & grid[i][j]\quad i=0,j=0               \\
                 & dp(i-1,j)+grid[i][j]\quad i\neq0,j=0  \\
                 & dp(i,j-1)+grid[i][j]\quad i=0,j\neq 0 \\
                 & max(f(i,j-1),f(i-1,j))+grid[i][j]     \\
            \end{cases}
        \end{split}
    \end{equation}
    对于上面的例子，从左上角到右下角，只能下移或者右移，求到右下角的礼物价值最大。从[0,0]位置1开始可以向下或者向右，如果向右礼物的最大和为11,如果向下礼物的最大和为13,如果上一步选择了向右，再次选择向右价值为11+3=14,以此类推可以得到一个和原始礼物矩阵同样大小的矩阵，矩阵的最大值在右下角：
    \begin{equation*}
        \begin{bmatrix}
            1  & 11 & 14 & 22 \\
            13 & 15 & 24 & 30 \\
            18 & 25 & 29 & 41 \\
            21 & 32 & 48 & 53
        \end{bmatrix}
    \end{equation*}
\end{example}
\cppfile[firstline=1,lastline=35]{code/DataStructAnd_Alg/src/maxValue.cpp}
时间复杂度为$O(m*n)$，空间复杂度为$O(m)$，（m表示矩阵的行数，n表示矩阵的列数）
\begin{example}[动态规划例子]
    \begin{figure}[H]
        \centering
        \includegraphics[width=0.5\textwidth]{ma_matrix.pdf}
        \caption{数值矩阵}
    \end{figure}
\end{example}
找出从起点起到底部的线路使得，线路上和最大。

方法一（递归）：
定义$D[r][c]$表示数组中位置为$r,c$的值。$f_{sum}(r,c)$表示从$D[r][c]$到底边的线路和的最大值。整个最大值计算过程可以归纳为：
\begin{equation*}
    f_{sum}(r,c)=
    \begin{cases}
        D[r][c]\quad r = N \\
        f_{sum}[r+1][c]+\max(D[r+1][c],D[r+1][c+1])
    \end{cases}
\end{equation*}
我们的目的是获取$f_{max}(0,0)$(第0行0列到底边的线路的和最大)的值,假设我们已经获得了$f_{max}(1,c)$到底边的最大值，我们的任务是选择$c$使得总值最大。这时候只需要在候选的$c=0$、$c=1$(当前列或者下一列)中选择最大值即可保证最大+最大获得的依旧是最大值，到第一行也是一样，如果我们获得了第2行到底边的最大值，则只需要选择合适的$c$即可，这里$c$只有两个选择，尽管上层$c$选择有两个，但是总归选一个，这里依旧是这样。反复如此到第$N$行，这时候到底边的值就直接等于此时值的位置。

方法二（转化递归节省资源）：
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\textwidth]{store_matrix.pdf}
    \caption{存储数值矩阵}
\end{figure}

\cppfile[firstline=1,lastline=27]{code/arith/ex13/test2.cc}
整个求解过程使用：
\begin{itemize}
    \item 找出最优解的性质，并刻画其结构特征。
    \item 递归地定义最优解的值
    \item 以自底而上的方式计算出最优值
    \item 根据计算最优值时得到的信息，构造一个最优解。
\end{itemize}
subsection{寻找最长不重复字串}
\begin{example}[寻找最长不重复字串]
    请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含'a'-'z'的字符。例如"arabcacfr"中，最长的不含重复字符的子字符串是"acfr",长度为4.
\end{example}
\textbf{思路：}
定义函数f(i)表示第i个字符为结尾的不包含重复的字符串的最长长度。我们从左到右扫描字符串中的每个字符。当我们计算以第i个字符为结尾的不包含重复字符的子字符串的最长长度为f(i)，我们已经知道了f(i-1)。
显然，如果第i个字符之前没有出现过，那么$f(i)=f(i-1)+1$。例如字符串"arabcacfr"中，显然f(0)等于1。在计算f(1)时，下标为1的字符'r'之前没有出现过，显然f(0)等于1。在计算f(1)时，下标为1的字符'r'之前没有出现过，因此f(1)等于2,即f(1)=f(0)+1。到目前为止，最长不含重复字符的子字符串是"ar"。

如果第i个字符之前已经出现过。我们先计算第i个字符和它上次出现在字符串中的位置的距离，并记为d，接着分两种情形分析。第一种是d小于或者等于f(i-1),此时第i个字符上次出现在f(i-1)对应的最长子字符串中，因此f(i)=d。于是这也意味着在第i个字符出现两次所夹的子字符串中在没有其它重复的字符了。在前面的例子中，我们继续计算f(2),即注意下标为2的字符'a'为结尾的不含重复字符的子字符串的最长长度。我们注意到字符'a'在之前出现过，该字符上次出现在下标为0的位置，它们之间的距离d为2.也就是字符串'a'出现在f(1)对应的最长不含重复字符的子字符串"ar"中，此时f(2)=d,即f(2)=2,对应的最长不含重复字符的子字符串是"ra"。

第二种情形是d大于f(i-1),此时第i个字符上次出现在f(i-1)对应的最长子字符串之前，因此仍然有f(i)=f(i-1)+1。我们接下来分析以字符串"arabcacgr"最后一个字符'r'为结尾的最长不含重复字符的子字符串的长度，即求f(8)。它以前的一个字符'f'为结尾的最长不含重复字符的子字符串是"acf"，因此f(7)=3。我们注意到最后一个字符'r'之前在字符串"arabcacfr"中出现过，上次出现在下标为1的位置，因此两次出现的距离d等于7,大于f(7)。这说明上一个字符'r'不再f(7)对应的最长不含重复字符的子字符串"acf"中，此时把字符'r'拼接到'acf'的后面也不会出现重复字符。因此f(8)=f(7)+1,即f(8)=4,对应的最长不含重复字符的子字符串为"acfr"。
\cppfile[firstline=1,lastline=24]{code/arith/ex60/main.cpp}
\subsection{袋鼠过河}
\begin{example}[袋鼠过河]
    一只袋鼠要从河这边跳到河对岸，河很宽，但是河中间打了很多桩子，每隔一米就有一个，每个桩子上都有一个弹簧，袋鼠跳到弹簧上就可以跳的更远。每个弹簧力量不同，用一个数字代表它的力量，如果弹簧力量为5，就代表袋鼠下一跳最多能够跳5米，如果为0，就会陷进去无法继续跳跃。河流一共N米宽，袋鼠初始位置就在第一个弹簧上面，要跳到最后一个弹簧之后就算过河了，给定每个弹簧的力量，求袋鼠最少需要多少跳能够到达对岸。如果无法到达输出-1
\end{example}
dp[i]表示到达i位置的最小步数，如果i位置前面的位置j，j+num[j]>=i说能能到达i的位置，就更新dp[i],保存达到i的最小步数。
\cppfile[firstline=1,lastline=23]{code/arith/ex61/main.cpp}
表示当位置j的跳数不为0的时候，到达i需要如何做？第一个可能是到达了j，因为num[j]的跳数比较大所以可能跳一此就超过i，或者可能是到达了dp[j]在跳一次超过了dp[i],这样这一跳就没有意义了，所以这里更新dp[i]的时候是取两者值更小的值作为最小跳跃次数。如果最后一个元素保持不变（10000）说明没有到达最后一个元素，这时候表示跳不到对岸。，否则跳到对岸的次数为跳到n的次数减1.
\subsection{目标和}
\begin{example}[目标和]
    给定一个非负整数数组，$a_1, a_2, \ldots, a_n$, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
    示例：
    \begin{Textcode}
        输入：nums: [1, 1, 1, 1, 1], S: 3
        输出：5
        解释：

        -1+1+1+1+1 = 3
        +1-1+1+1+1 = 3
        +1+1-1+1+1 = 3
        +1+1+1-1+1 = 3
        +1+1+1+1-1 = 3

        一共有5种方法让最终目标和为3。
    \end{Textcode}
\end{example}
我们用 dp[i][j] 表示用数组中的前 i 个元素，组成和为 j 的方案数。考虑第 i 个数 nums[i]，它可以被添加 + 或 -，因此状态转移方程如下：
\begin{equation*}
    dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]
\end{equation*}
该公式的含义为：我们想通过nums数组的前i个元素的和组成j，我们假设前i-1个数已经确定，通过+nums[i]或者-nums[i]求和，也可以写成递推的形式：
\begin{align*}
    dp[i][j + nums[i]] & += dp[i - 1][j] \\
    dp[i][j - nums[i]] & += dp[i - 1][j]
\end{align*}
由于数组中所有数的和不超过 1000，那么 j 的最小值可以达到 -1000。在很多语言中，是不允许数组的下标为负数的，因此我们需要给 dp[i][j] 的第二维预先增加 1000将求和的结果移动到数组中下标为正的区域，即：
\begin{align*}
    dp[i][j + nums[i] + 1000] & += dp[i - 1][j + 1000] \\
    dp[i][j - nums[i] + 1000] & += dp[i - 1][j + 1000]
\end{align*}
我们希望获取数组[2,1,1,2]组合为0的所有可能数。DFS搜索如\figref{fig:dp_nums}
\begin{figure}[!htbp]
    \centering
    \includegraphics*[width=\textwidth]{dp_nums}
    \caption{DFS 搜索目标和的可能数}
    \label{fig:dp_nums}
\end{figure}
使用DFS搜索解的个数容易超时，这里使用动态规划的方法示意图如\figref{fig:dp_nums_solve}
\begin{figure}[!htbp]
    \centering
    \includegraphics*[width=\textwidth]{dp_nums_solve}
    \caption{动态规划求解过程}
    \label{fig:dp_nums_solve}
\end{figure}
DP[i][j]表示nums数组索引i和其之前的所有元素通过（+、-）计算得到j的组合数。为了更好的存储数组，我们将数组下标范围[-6,6]转换到[0,12]。对于DP数组中元素DP[0][-2]（新的坐标下为DP[0][4]）只存在（0-2=-2这一种情况），所以DP[0][4]=1。
因为DP[i][j-nums[i]]+DP[i][j+nums[i]]，后续的结果均可以通过推导得到。例如DP[2][4]=DP[1][2]+DP[1][6]。
\cppfile{code/DataStructAnd_Alg/src/findTargetSumWays.cpp}
\subsection{股票的买卖时机}
\begin{example}{股票的买卖时机}
    给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。

    [7,1,5,3,6,4]
\end{example}
\begin{Mind}{股票的买卖时机}{}
    f(n)表示价格数组前n个数通过股票买卖获得的最大利润。假设我们已经知道了f(n-1)的最大价格，和前n个数的最小值min\_value。对于第i个价格prices[i]，是否买卖取决于今天卖的收益能否增加。即prices[i]-min\_value（减去之前的最小数才能获得最大收益）是否比f(n-1)更大。即f(n)=max(f(n-1),prices[i]-min\_price)。为了计算方便我们可以缓存f(n-1)用于f(n)的计算。
\end{Mind}
\cppfile[firstline=5,lastline=21]{code/DataStructAnd_Alg/src/maxProfit.cpp}
可以多次买卖条件下求股票的最大价值。
\begin{Mind}{多次买卖条件股票最大价值}{}
    股票价格总是在上升区间或者下降区间。我们只需要找到上升区间的开始和结束点就可以求的当前这段时间的股票最大价值。我们找到所有上升区间的最小值和最大值，他们的价格差就是最大股票价值。判断上升区间（找到位置i的第一个元素，prices[i+1]>=prices[i]这个i就是上升的起点，下降的起点可以通过同样的方式找到。）然后累计差即可得到最终最大价值，
\end{Mind}
\cppfile[firstline=22,lastline=43]{code/DataStructAnd_Alg/src/maxProfit.cpp}
\subsection{剪绳子}
\begin{example}{剪绳子}
    给定一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1且m>1），每段绳子的长度记为k[0]、k[1]、…… 、k[m]。请问$k[0]\times k[1]\times\cdots\times k[m]$可能的最大乘积是多少？例如，当绳子的长度为8时，我们把它建成长度分别为2、3、3的三段，此时得到的最大乘积是18。
\end{example}
\begin{Mind}{剪绳子思路}{}
    定义函数$f(n)$ 为把长度为n的绳子剪成若干段后各段长度的乘积的最大值。在剪第一刀的时候我们有n-1种可能选择，剪出的第一段长度为$1,2,\cdots,n-1$。因此$f(n)=max(f(i)\times f(n-i))$，i表示剪绳子的位置，其中$0<i<n$。
\end{Mind}
对于不同长度的绳子经过剪断求乘积得到的结果分析如下：
\begin{enumerate}
    \item f(1)：无法剪，结果为0。
    \item f(2)：剪两端，结果为1。
    \item f(3)：剪成1和2或者3个1，结果为2。
    \item f(4)：剪成2、2或者1、3，或者1、2、1，结果为4。
\end{enumerate}
假设现在我们对绳子分成$n$份，每一份的长度为$x_i$。现在我们希望求的函数$f(x)=x_1\cdot x_2\cdots x_n$的最大值。因为有：
\begin{equation}
    \frac{x_1+x_2+\cdots+x_n}{n}\geq\sqrt[n]{x_1\cdot x_2\cdots x_n}
\end{equation}
等号成立的条件是$x_1=x_2=\cdots=x_n$。即$\sqrt[n]{x_1\cdot x_2\cdots x_n}$x项获得最大值$\left(\frac{x_1+x_2+\cdots+x_n}{n}\right)^n$，需要保证$\sqrt[n]{x_1\cdot x_2\cdots x_n}$，这样我们假设绳子被分割成$a$段。则有$a=\frac{n}{x}$（x是每一段的长度）。这样我们需要求使得：
\begin{align*}
    f(x)  & = x^{\frac{n}{x}}    \\
    f'(x) & = 0\rightarrow x = e
\end{align*}
因为$x$必须为整数，所以x为2或者3。因为3离2更接近，为3是$f(x)$值更大。也就是说，长度为n的绳子，如果能平均分成3的整数倍即可得到乘积最大($n = 3\times k+r$)。如果余1，则可以拿一个长度为3的两者组合为两个长度为2的结果（$2\times2\>1\times 3$）。当余2的时候则直接返回$3^k\times2$。
\cppfile[firstline=1,lastline=49]{code/DataStructAnd_Alg/src/maxProductCutting.cpp}
\subsection{背包客问题}
\begin{example}{0-1背包客问题}
    有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。

    定义一个二维数组 dp 存储最大价值，其中 $dp[i][j]$ 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。设第 i 件物品体积为 w，价值为 v，根据第 i 件物品是否添加到背包中，可以分两种情况讨论：

    第 i 件物品没添加到背包，总体积不超过 j 的前 i 件物品的最大价值就是总体积不超过 j 的前 i-1 件物品的最大价值，$dp[i][j] = dp[i-1][j]$。
    第 i 件物品添加到背包中，$dp[i][j] = dp[i-1][j-w] + v$。
    第 i 件物品可添加也可以不添加，取决于哪种情况下最大价值更大。因此，0-1 背包的状态转移方程为：
    \[dp[i][j]=max(dp[i-1][j],dp[i-1][j-w_i])+v_i\]
    \textbf{刻画0-1背包问题的最优解的结构}
    可以将背包问题的求解过程看作是进行一系列的决策过程，即决定哪些物品应该放入背包，哪些物品不放入背包。如果一个问题的最优解包含了物品n，即$x_n=1$，那么其余$x_1,x_2,\ldots，x_{n-1}$一定构成子问题1，2，...，n-1在容量$W-w_n$时的最优解。如果这个最优解不包含物品n，即$x_n=0$，那么其余$x_1,x_2,\ldots,x_{n-1}$一定构成子问题1，2，...，n-1在容量W时的最优解。
    \textbf{递归定义最优解的值}
    根据上述分析的最优解的结构递归地定义问题最优解。设$dp[i,w]$表示背包容量为$W$时，$i$个物品导致的最优解的总价值，得到下式。显然要求$dp[n,W]$。
    \begin{equation*}
        dp[i,w] =
        \begin{cases}
            0\quad i=0\ or\ w=0  \\
            dp[i-1,w]\quad w_i>w \\
            max\{dp[i-1,w-w_i]+v_i,dp[i-1,w],i>0\ and\ w_i\leq w\}
        \end{cases}
    \end{equation*}
    文字描述为：在i个物品中为了获重量不超过$W$的最大价值$dp[i,W]$,这个问题分为两步考虑，假设在i-1个物品中我们获得了最大价值$w_1$,完成这个任务，下一步可以选择第i个物品，但是第i个物品的重量$w_i$可能出现让重量超过W的情况，这个时候的最优解其实还是i-1的最优解$dp[i-1,W]$,如果这个时候的重量$w_i$没有超过W呢？这时候结果的最大价值为$dp[i-1,W-w_i]+v_i$为什么是$W-w_i$?因为需要时刻保持重量不超标，也就是说如果之前的$dp[i-1,W]$表示不超过$W$但是如果离$W$的距离小于$w_i$拿下一个物品就超重了。假设条件$n=5,W=17$,物品价值表如下\tabref{tab:nkpack}:
    \begin{table}[!htbp]
        \centering
        \caption{物品价值和重量}
        \begin{tabular}{llllll}
            \toprule
            物品编号 & 1 & 2 & 3  & 4  & 5  \\
            \midrule
            重量w    & 3 & 4 & 7  & 8  & 9  \\
            价值v    & 4 & 5 & 10 & 11 & 13 \\
            \bottomrule
        \end{tabular}
        \label{tab:nkpack}
    \end{table}
\end{example}
\cppfile[firstline=1,lastline=16]{code/offer/ex15/main.cpp}
\subsection{最长递增子序列}
给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的），例如：
\begin{Textcode}
    输入
    [2,1,5,3,6,4,8,9,7]
    返回值
    [1,3,4,8,9]
    示例2
    [1,2,8,6,4]
    返回值
    复制
    [1,2,4]
\end{Textcode}

\subsection{零和一}
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
\begin{Textcode}
    示例 1：

    输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
    输出：4
    解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
    其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
\end{Textcode}
\begin{itemize}
    \item 状态：DP[i][m][n]表示输入字符串数组中从起点0到终点i的字符串中符合$num(0)\leq m$同时$num(1)
              \leq n$的最大元素。
    \item 转移方程：
          \begin{equation*}
              DP[i][m][n] = max(DP[i-1][m][n],DP[i][m-num[0]][n-num[1]]+1)
          \end{equation*}
          其中$DP[i][m-num[0]][n-num[1]]+1$ 表示字符串被选中、然后贡献了一定的0和1。之后依然符合条件0和1的数量不超过m和n。
    \item 边界条件：字符串长度为0的时候结果为0。
\end{itemize}
\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{zeros_and_ones}
    \caption{零和一计算示意图}
\end{figure}
自底向上实现：
\cppfile{code/algorithm/src/findMaxForm.cpp}
\section{贪心算法}
\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{activity_max_num}
    \caption{可安排最大会议数}
    \label{fig:activity_max_num}
\end{figure}
现在有会议的开始和结束时间，11组会议，需要知道如何能安排最多的会议。例如活动$a_1$表示会议的开始和结束时间分别是1、4。会议安排的表格如下\figref{tab:activity_num}
\begin{table}[!htbp]
    \caption{会议安排时间}
    \centering
    \begin{tabular}{cccccccccccc}
        \toprule
        index                & 1 & 2 & 3 & 4 & 5 & 6 & 7  & 8  & 9  & 10 & 11 \\
        \midrule
        开始时间 $s_{index}$ & 1 & 3 & 0 & 5 & 3 & 5 & 6  & 8  & 8  & 3  & 12 \\
        结束时间 $f_{index}$ & 4 & 5 & 6 & 7 & 9 & 9 & 10 & 11 & 12 & 14 & 16 \\
        \bottomrule
    \end{tabular}
    \label{tab:activity_num}
\end{table}
会议的结束时间越早，越有可能给后面的会议安排（可安排的会议越多）。我们先对会议的结束时间从小到大排序，选中会议结束时间最早的会议，然后在剩下的会议集合中寻找刚好开始时间在其之后的会议，反复筛选直到最后一个会议。算法流程如下\figref{fig:activity_executable}
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=\textwidth]{activity_executable}
    \caption{会议室安排流程}
    \label{fig:activity_executable}
\end{figure}
更容易理解的办法是插入一个终点为0的开始结束时间对，但是从实现的角度往vector插入代价比较高，所以代码实现的时候使用了看起来不怎么优雅的为0判断然后再次操作。
\cppfile[firstline=2,lastline=20]{third_party/coding/cxx/algorithm/src/activitySelect.cpp}
\subsection{跳跃游戏}
\begin{Textcode}
    给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

    数组中的每个元素代表你在该位置可以跳跃的最大长度。

    判断你是否能够到达最后一个下标。



    示例 1：

    输入：nums = [2,3,1,1,4]
    输出：true
    解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
    示例 2：

    输入：nums = [3,2,1,0,4]
    输出：false
    解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
\end{Textcode}
从起点开始，起点的数值决定了能跳多远。例如 nums[0] = 2 表示了在0这个位置最远能跳到位置2。对于那如果跳到位置1之后呢？可以跳到4（1+3），如果跳到2则只能跳到3（1+2）。所以需要从开头第一个元素到倒数第二个元素获取其能跳到的最远距离，如果距离超过了最后一个元素的下标则能跳到，否则不能。这里有一个错误思路(判断i+num[i]是否超过最后一个元素位置的下标，错误在于你可能没法到达某一下标，比如：[0,1,2]，当你在0的时候你没法到达其它下标，直接为false，但是1能跳一下到目的地。)
\cppfile[firstline=2,lastline=20]{third_party/coding/cxx/algorithm/src/canJump.cpp}

\section{位运算问题}
\subsection{开关灯}
\begin{example}[开关灯]
    有100栈灯，分别一次对所有灯的$1，2,3,\ldots，n$的倍数的等取反（开变成关，关变成开），求100此操作后亦然开着的灯。
\end{example}
\cppfile[firstline=1,lastline=9]{code/arith/ex68/main.cpp}
\section{设计部分}
\subsection{实现数据结构栈}
\begin{example}[实现最小栈数据结构]
    通过两个栈存放数据，m\_data,m\_min分别用来存放原始入栈数据和最小值。使得pop，push，min时间复杂度为O(1)
\end{example}
\cppfile[firstline=1,lastline=36]{code/arith/ex25/main.cpp}
\subsection{用栈实现队列}
\begin{example}[用栈实现队列]
    栈是先入后出，队列是先入先出。用栈实现队列实现先入先出。
    \begin{itemize}
        \item push(x)：将一个元素放入队列的尾部。
        \item pop(x)：从队列首部移除元素。
        \item peek()：返回队列首部的元素。
        \item empty()：返回队列是否为空。
    \end{itemize}
\end{example}
通过两个栈实现将先入后出转化为先入先出。一个数据栈用了存放数据，一旦有peek操作，则将数据栈里面的元素放入另一个栈（第二个栈出栈实现先入先出）。
\cppfile{code/DataStructAnd_Alg/src/MyQueue.cpp}
\subsection{用队列实现栈}
\begin{example}[队列实现栈]
    用先入先出的队列实现先入后出的栈。
\end{example}
定义队列存储数据，入栈的时候如果队列为空则直接将元素如队列，否则将元素入队列之后将入队列之前的元素出队列然后重新入队。实现一个队列先入后出。push操作时间复杂度$O(n)$其它时间和空间复杂度都为$O(1)$。

\cppfile{code/DataStructAnd_Alg/src/MyStack.cpp}
\section{数学计算}
\subsection{求平方根}
\begin{Mind}{牛顿迭代法计算平方根}{}
    $f(x) = x^2-n$当函数表达式为0是求的的结果$x$即$\sqrt{n}$。假设给定一个$x_i$可以计算得到$f(x_i)=x_i^2-n$这个结果不一定为0（为0则$x_i$为所求解）。下一步计算该点切线方程和$x$轴的交点$x_{i+1}$同样计算此时的$f(x_{i+1})=x_{i+1}^2-n$，这时候$f(x_{i+1})$结果依然不一定为0,以新的$x_{i+1}$作为下一个计算点，反复迭代计算直到$x_{n}\approx x_{n-1}$或者是$f(n)=0$。当给定$x_i$时经过$x_{i}$的直线方程为：$y = f(x_i)+f'(x_i)(x-x_i)$切线方程为0求的下一个迭代点$x_{i+1}=x_i-\frac{f(x_i)}{f'(x_i)}=x_i-\frac{x_i^2-n}{2x_i}=\frac{1}{2}(x_i+\frac{n}{x_i})$。
\end{Mind}
牛顿迭代法：
\begin{figure}[!htbp]
    \centering
    \begin{tikzpicture}[scale=0.7]
        \draw [help lines] (0,0) grid (8,9);
        \draw[<->,thick] (0,9) -- (0,0) -- (8,0);
        \draw[blue,ultra thick,domain=1:3.2] plot (\x,{\x*\x-2});
        \node[below right] at (3.3,7) {切点$x_i$};
        \draw[ultra thick,cyan,dashed] (0,7) node [left]{$f(x_i)$}--(3,7) node [left] {} --(3,0) node[above right] {$x_i$};
        \draw[ultra thick,cyan,dashed] (0,1.34) node [left]{$f(x_{i+1})$}--(1.83,1.34) node [left] {} --(1.83,0) node[below right] {$x_{i+1}$};
        \draw[red,ultra thick,domain=1.833:3] plot (\x,{6*\x-11});
        \draw[fill=red] (3,7) circle [radius=0.1];
        \draw[fill=red] (1.83,1.34) circle [radius=0.1];
        \draw[fill=green] (1.8,0) circle [radius=0.1];
        \node[below] at (5,8){$f(x)=x^2-2$};
        \node[below] at (8,0){$x$};
        \node[left] at (0,9){$f(x)$};
    \end{tikzpicture}
    \caption{求解平方根示意图}
    \label{fig:sqrt}
\end{figure}
\cppfile{code/algorithm/src/sqrt.cpp}
\section{其它}
\subsection{丑数}
\begin{example}[丑数]
    给定数值n输出从小到大排序的丑数n个。
\end{example}
\cppfile[firstline=1,lastline=36]{code/arith/38/main.cpp}

\subsection{输出最小的k个数}
\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{min_kth.pdf}
    \caption{最小前k个数处理流程}
\end{figure}
时间复杂度O(n):
\cppfile[firstline=1,lastline=37]{code/arith/ex34/main.cpp}
Partition二分思想：如果我们使用partition对数组操作，轴值坐标的元素全小于轴值,右边全大于轴值。那么如果左边的元素正好为k就可以输出最小的k个数。如果左边的元素大于k，下次应该在坐标划分，否则应该在右边划分。
\cppfile{code/algorithm/src/smallestK.cpp}
\subsection{空间复杂度为1判断数字是不是回文数字}
\begin{example}[判断回文数字]
    判断回文数字，如12321是回文，123不是，回文数字关于数字中心对称。\\
    \textbf{思路：}用一个变量存储数字最高位，判断最高位，判断最低为和最高位是否相等，相等则删除最高位和最低为继续比较，循环结束的条件为这个数字小于0.
\end{example}
\cppfile[firstline=1,lastline=18]{code/arith/ex47/main.cpp}
\subsection{后缀表达式转换}
中缀表达式转换为后缀表达式：
\begin{enumerate}
    \item 创建符号栈存储符号，表达式栈存储表达式。
    \item 扫描中序表达式：
          \begin{enumerate}
              \item 是数字，直接入表达式栈。
              \item 是符号：
                    \begin{enumerate}
                        \item '('：入符号栈
                        \item ')':将符号栈中的元素依次取出加入表达式栈。
                        \item 其它符号，将符号栈中的元素依次出栈，进入表达式栈，直到遇到比当前符号优先级更低的符号或者'('。
                    \end{enumerate}
          \end{enumerate}

    \item 将符号栈的元素分别取出加入表达式栈。
\end{enumerate}
对于表达式：3+(2-5)*6/3，后缀表达式计算过程如下：
\begin{enumerate}
    \item 数字3入表达式栈。
    \item 符号‘+’，入符号栈（当前栈中不存在优先级大于当前符号的操作符号）。
    \item 符号‘（’，直接入符号栈。
    \item 数字2，入表达式栈。
    \item 符号-，入符号栈（当前栈中不存在优先级大于当前符号的操作符号）。
    \item 数字5，入表达式栈。
    \item 符号‘)’，将表达式中符号出栈同时入表达式栈，直到遇到‘(’。
    \item 符号‘*’，当前符号操作优先级高于符号栈里面的‘+’，入符号栈。
    \item 数字6，入表达式栈。
    \item 符号‘/’，入符号栈（当前操作符和栈顶元素优先级别相同 ，弹出栈顶元素）。
    \item 将符号栈里面的元素出栈添加到表达式栈。
\end{enumerate}
出入栈流程如\figref{fig:pos_exp}:
\begin{figure}[!htbp]
    \centering
    \includegraphics[width=0.8\textwidth]{pos_exp}
    \caption{后缀表达式计算流程}
    \label{fig:pos_exp}
\end{figure}
\cppfile[firstline=1,lastline=34]{code/arith/ex64/main.cpp}
\subsection{后缀表达式计算}
\begin{example}[后缀表达式输出]
    扫描表达式，如果遇到“+”、“-”、、“*”、“/”将元素加入操作栈，如果是操作数则加入到后缀表达式，如果是"("也压入，但是当扫描的表达式出现")"的时候去要将操作数里面的内容全部出栈加入表达式。对于表达式(A+B*C)/D的后最表达式计算过程
    后缀表达式计算过程：将元素数据放入数据栈，操作放入操作栈，遇到操作就出栈，操作符是几元就出栈几个元素然后将元素计算后的结果放入数据栈继续扫描知道结束。
    \begin{figure}[H]
        \centering
        \includegraphics[width=\textwidth]{pos_express}
        \caption{后缀表达式计算}
    \end{figure}
\end{example}
\cppfile[firstline=1,lastline=34]{code/arith/ex64/main.cpp}

